首页 > 试题广场 >

从尾到头打印链表

[编程题]从尾到头打印链表
  • 热度指数：1705347 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000
示例1

输入

{1,2,3}

输出

[3,2,1]
示例2

输入

{67,0,24,58}

输出

[58,24,0,67]

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
徘徊的路人甲头像 徘徊的路人甲
方法一：链表从尾到头输出，利用递归实现，不使用库函数直接printf输出的时候用递归比较好 
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> value;
        if(head != NULL)
        {
            value.insert(value.begin(),head->val);
            if(head->next != NULL)
            {
                vector<int> tempVec = printListFromTailToHead(head->next);
                if(tempVec.size()>0)
                value.insert(value.begin(),tempVec.begin(),tempVec.end());  
            }         
            
        }
        return value;
    }
};
方法二：用库函数，每次扫描一个节点，将该结点数据存入vector中，如果该节点有下一节点，将下一节点数据直接插入vector最前面，直至遍历完，或者直接加在最后，最后调用reverse 
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> value;
        if(head != NULL)
        {
            value.insert(value.begin(),head->val);
            while(head->next != NULL)
            {
                value.insert(value.begin(),head->next->val);
                head = head->next;
            }         
            
        }
        return value;
    }
};

编辑于 2015-06-18 16:53:34 回复(73)
Java
牛客499848474号头像 牛客499848474号
笨一点先反转链表，再打印
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null) {
            return new ArrayList<>();
        }
        ArrayList<Integer> result = new ArrayList<Integer>();
        ListNode prev = null;
        ListNode cur = listNode;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        while(prev != null){
            result.add(prev.val);
            prev = prev.next;
        }
        return result;
    }
}
发表于 2024-09-13 15:22:29 回复(0)
Java
Helen201808092219239头像 Helen201808092219239 
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> initLinkedList = new ArrayList<>();
        ListNode temptNode = listNode;
        while (temptNode != null) {
            initLinkedList.add(temptNode.val);
            temptNode = temptNode.next;
        }
        temptNode = listNode;
        ArrayList<Integer> reversedLinkedList = new ArrayList<>();
        ListNode reversedListNode = reversedLinkedList(listNode);

        while (reversedListNode != null) {
            reversedLinkedList.add(reversedListNode.val);
            reversedListNode = reversedListNode.next;
        }

        return reversedLinkedList;

    }
    public static ListNode reversedLinkedList(ListNode listNode) {
        if (listNode == null || listNode.next == null) {
            return listNode;
        } else {
            ListNode temptNode = listNode;
            ListNode priorNode = null;
            ListNode nextNode = listNode.next;
            while (nextNode.next != null) {
                priorNode = temptNode;
                temptNode = nextNode;
                nextNode = nextNode.next;
                temptNode.next = priorNode;
            }
            nextNode.next = temptNode;
            listNode.next = null;
            listNode = nextNode;
            return listNode;
        }
    }
}

编辑于 2024-02-17 17:45:21 回复(0)
Java
牛客426635438号头像 牛客426635438号

1.利用头插法直接逆置链表

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList printListFromTailToHead(ListNode listNode) {
        if(listNode == null){
            return new ArrayList();
        }
        ListNode next = null;
        ListNode prev = null;
        while(listNode != null){
            next = listNode.next;
            listNode.next = prev;
            prev = listNode;
            listNode =next;
        }
        listNode = prev;
        ArrayList reslut = new ArrayList();
        while(listNode != null){
            reslut.add(listNode.val);
            listNode = listNode.next;
        }
        return reslut;
    }
}

2.新建数组保存值，之后逆置数组

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> resultList = new ArrayList<>();
       while(listNode != null){
        resultList.add(listNode.val);
        listNode = listNode.next;
       }
       ArrayList<Integer> midList = new ArrayList<>();
       for(int i = resultList.size()-1; i >= 0;i--){
        midList.add(resultList.get(i));
       }

       return midList;   
    }
}
发表于 2023-12-17 15:28:51 回复(0)
Java
想潜水的大白菜在努力头像 想潜水的大白菜在努力 
最优解：链表利用数组原地翻转
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //原地调换位置(链表反转)
        if(listNode == null){
            return new ArrayList<Integer>(0);
        }
        int count = 0;
        ListNode tmp = listNode;
        while(tmp != null){
            count++;
            tmp = tmp.next;
        }
        int[] res = new int[count];
        int k = count - 1;
        while(listNode != null){
            res[k--] = listNode.val;
            listNode = listNode.next;
        }
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 0;i < res.length;i++){
            arr.add(res[i]);
        }
        return arr;
    }
}


发表于 2023-11-05 00:02:58 回复(0)
Java
RealBall头像 RealBall 
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 方法四：利用头插法 
        ListNode head=new ListNode(-1) ;
        while(listNode!= null){
               //把新加入的节点当做node
               ListNode temp=listNode.next; //需要先把下一个节点的值存储起来，不然就会失效
               listNode.next=head.next;
               head.next=listNode;
               listNode=temp;
        }
        ArrayList <Integer> res = new ArrayList<Integer>();
        head=head.next; 
        while(head!=null){  //访问这个新链表的值即可
            res.add(head.val);
            head=head.next;
        }
        return res;


/*
        // 方法三：利用递归 访问改节点则需访问该节点的子节点
         ArrayList <Integer> res=new ArrayList<Integer>();//定义在方法外边

        if (listNode != null) {
            printListFromTailToHead(listNode.next);
            res.add(listNode.val);
        }
        return res;


        // 方法二：利用Aarraylist.add( index,value)方法来实现
        
        ArrayList <Integer> res=new ArrayList<Integer>();
        while (listNode!=null){
        res.add(0,listNode.val);
        listNode=listNode.next;
        }
        return res;
        

             //方法一：利用栈，从头到尾依次入栈，然后依次出栈
             ArrayList<Integer> res=new ArrayList<Integer>();
             Stack<ListNode> stack =new Stack<ListNode>();
             while(listNode != null){
                 stack.add(listNode);
                 listNode=listNode.next;
             }
             while(stack.size()>0){
                 res.add(stack.pop().val);
             }
             return res;

          */



    }
}

发表于 2023-08-28 17:45:57 回复(0)
Java
SUMMERENT头像 SUMMERENT 
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList();
        while(listNode!=null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}

发表于 2023-06-14 10:02:53 回复(0)
Java
终焉之志头像 终焉之志
ArrayList本身也可以实现类似栈的功能，list.add(0, xxx)即可插入头部
这样的话代码就非常简洁，只需遍历链表，每个节点的值从头插入数组即可 
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(listNode != null){
            res.add(0,listNode.val);
            listNode = listNode.next;
        }
        return res;
    }
}



发表于 2023-06-10 10:16:45 回复(0)
Java
帅的烦燥头像 帅的烦燥
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

           ArrayList<Integer> list=new ArrayList<Integer>();
           if(listNode!=null){
               getList(list,listNode);
           }
           return list;
        
    }

    public ArrayList<Integer>  getList(ArrayList<Integer> list,ListNode listNode){
          if(listNode.next==null){
              list.add(listNode.val); 
              return list;
          }else{
              list=getList(list,listNode.next);
              list.add(listNode.val);
              return list;
          }
    }
}
发表于 2022-12-01 19:47:09 回复(0)
Java
小松鼠涛声依旧头像 小松鼠涛声依旧
import java.util.*;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        while(listNode != null) {
            res.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(res);
        return res;
    }
}
发表于 2022-09-15 14:11:55 回复(0)
Java
wangmeichen头像 wangmeichen
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while(listNode!=null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}
发表于 2022-08-31 16:00:20 回复(0)
Java
圣光·明流火头像 圣光·明流火 
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList();
        while(listNode != null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}

发表于 2022-08-24 17:29:42 回复(0)
Java
牛客461316693号头像 牛客461316693号 
public class Solution {
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        reserve(listNode);
        return list;
    }

    private void reserve(ListNode listNode) {
        if (listNode == null) {
            return;
        }
        reserve(listNode.next);
        list.add(listNode.val);
    }
}

发表于 2022-08-17 11:11:00 回复(0)
Java
爱睡觉的杨大爷头像 爱睡觉的杨大爷 
import java.util.*;
 
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //多使用一个栈的数据结构，使节点值逆序
        //时间复杂度为O(N),空间复杂度O(N)
        Stack<Integer> s=new Stack<Integer>();
        ArrayList<Integer> res=new ArrayList<>();
        while(listNode!=null){
            s.push(listNode.val);
            listNode=listNode.next;
        }
        while(!s.isEmpty()){
            res.add(s.pop());
        }
        return res;
    }
}

发表于 2022-07-30 12:37:15 回复(0)
Java
老天眷顾眷顾我吧头像 老天眷顾眷顾我吧
为什么和答案同样的代码 会显示报错，说数组溢出，多点几次提交又可以了。。。
发表于 2022-07-23 21:37:16 回复(0)
Java
牛客434675046号头像 牛客434675046号
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList data = new ArrayList<Integer>();
        ListNode cur = listNode;
        while (cur != null) {
            data.add(cur.val);
            cur = cur.next;
        }
        Collections.reverse(data);
        return data;
    }
}
发表于 2022-07-18 22:21:00 回复(0)
Java
txy_钟琛头像 txy_钟琛 
import java.util.Collections;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> ans = new ArrayList<>();
        printListFromTailToHeadCore(ans,listNode);
        return ans;
    }

    private void printListFromTailToHeadCore(ArrayList<Integer> ans, ListNode listNode) {
        if (listNode == null){
            return;
        }
        printListFromTailToHeadCore(ans,listNode.next);
        ans.add(listNode.val);
    }
}

发表于 2022-05-23 11:43:43 回复(0)
Java
牛客708435190号头像 牛客708435190号 
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> listres= new ArrayList();
        while(listNode != null){         
            int i = 0;
            listres.add(i,listNode.val);
            i++;
            listNode = listNode.next;
        }
        return listres;
    }
}

发表于 2022-04-23 05:18:38 回复(1)
提交观点

问题信息

链表
来自：校招模拟卷
难度：
394条回答 562484浏览

热门推荐

通过挑战的用户

查看代码

相关试题

从尾到头打印链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号