首页 > 试题广场 >

从尾到头打印链表

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

如输入{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)
grass_stars头像 grass_stars 
java 递归超简洁版本
public class Solution {
    ArrayList<Integer> arrayList=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		if(listNode!=null){
			this.printListFromTailToHead(listNode.next);
			arrayList.add(listNode.val);
		}
		return arrayList;
    }
}

编辑于 2015-08-03 00:59:00 回复(267)
菩提旭光头像 菩提旭光
最佳代码：代码思路借助栈，遍历的时候入栈，由于数据结构中栈的特点是先进后出，所以遍历的过程中压栈，推栈，完了弹栈加到ArrayList中。有两个容易出错的地方：第一，第一次测试用例，{}返回[ ],null是null，而[ ]是new ArrayList（）但是没有数据。第二，遍历stack用的方法是！stak.isEmpty()方法，而不是for循环size遍历。。
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null){
            ArrayList list = new ArrayList();
            return list;
        }
        Stack<Integer> stk = new Stack<Integer>();
        while(listNode != null){
            stk.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> arr = new ArrayList<Integer>();
        while(!stk.isEmpty()){
            arr.add(stk.pop());
        }
        return arr;
    }
}
编辑于 2015-08-24 18:00:57 回复(17)
GEZOX__头像 GEZOX__ 
# python的实现这么少， 我来添砖加瓦
# 1.先遍历链表元素到栈
# 2.栈再弹出




# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        lst,lst_bak = [],[]
        if not listNode:
            return lst
        while listNode:
            lst.append(listNode.val)
            listNode = listNode.next
        while lst:
            lst_bak.append(lst.pop())
        return lst_bak

编辑于 2018-01-29 15:00:53 回复(7)
就多贡献python代码吧头像 就多贡献python代码吧 

	# -*- coding:utf-8-*-





	# classListNode:





	#     def __init__(self, x):





	#         self.val = x





	#         self.next = None





	 





	classSolution:





	    # 返回从尾部到头部的列表值序列，例如[1,2,3]





	    def printListFromTailToHead(self, listNode):





	        # write code here





	        result = []





	        iflistNode is None:





	            returnresult





	             





	        whilelistNode.next is not None:





	            result.extend([listNode.val])





	            listNode=listNode.next





	        result.extend([listNode.val])





	         





	        returnresult[::-1]

发表于 2016-03-20 23:17:20 回复(15)
老石基头像 老石基 
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(listNode==null)
            return list;
        get(listNode, list);
        return list;
    }
	public void get(ListNode listNode,ArrayList<Integer> list){
		if(listNode.next==null){
			list.add(listNode.val);
			return;
		}
		get(listNode.next, list);
		list.add(listNode.val);
	}
}

发表于 2016-04-14 20:40:37 回复(1)
Exe头像 Exe
利用头插arraylist实现栈的功能
 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
   if(listNode == null)
   return list;
   while(listNode.next != null){
list.add(0,listNode.val);
listNode = listNode.next;
}
list.add(0,listNode.val);
return list; 
    }

发表于 2015-09-01 12:15:04 回复(5)
luochangan头像 luochangan 
public class LinkedList {
	public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode list = new ListNode(0);
        
        ListNode cursor = listNode;
        ListNode top = list;
       
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        while(cursor!=null){
        	   ListNode temp = new ListNode(cursor.val);
               temp.next = top;
               top = temp;
               cursor = cursor.next;
        }
        
        while(top!=null){
     		result.add(top.val);      
            top = top.next;
        }
        result.remove(result.size()-1);
        
      return result;
     
    }

}

编辑于 2015-08-06 16:04:52 回复(4)
Java
烫杯藕粉头像 烫杯藕粉
有反转思想，我们就可以试着用栈来处理。
先将所有节点的值压入栈中。
再从栈中弹出。
就可以达到reverse的效果。 
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //用来存储链表中节点的值。
        Stack<Integer> reverse = new Stack<>();
        while(listNode != null){
            reverse.push(listNode.val);
            listNode = listNode.next;
        }
        //创建的题目要求的数据类型来存储反向的节点值。
        ArrayList<Integer> result = new ArrayList<>(); 
        while(!reverse.isEmpty()){
            //将值从栈中弹出，并添加到ArrayList中
            result.add(reverse.pop());
        }
        return result;
    }
}


发表于 2021-08-06 18:17:21 回复(1)
Java
御坂美琴2604头像 御坂美琴2604
有点忘了 链表是啥了。。。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        for(;listNode != null;) {
            list.add(0, listNode.val);
            listNode = listNode.next;
        }
        return list; 
    }

发表于 2017-09-04 13:49:53 回复(1)
writezen头像 writezen 
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

 Stack<ListNode> stack = new Stack<ListNode>();
 ArrayList<Integer> list=new ArrayList<Integer>();
 ListNode current=listNode;
 while(current!=null){
 stack.push(current);
 current=current.next;
 }
 while(!stack.isEmpty()){
 list.add(new Integer(stack.pop().val));
 }
 
 return list;

 }
}

发表于 2015-04-09 20:55:24 回复(3)
Java
牛客906517231号头像 牛客906517231号
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
    /*
    // 方法一：先进后出，我们可以想到栈
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //用来存储链表中节点的值。
        Stack<Integer> reverse = new Stack<>();
        while(listNode != null){
            reverse.push(listNode.val);
            listNode = listNode.next;
        }
        //创建的题目要求的数据类型来存储反向的节点值。
        ArrayList<Integer> result = new ArrayList<>(); 
        while(!reverse.isEmpty()){
            //将值从栈中弹出，并添加到ArrayList中
            result.add(reverse.pop());
        }
        return result;
    }
    */
    
    /* 
    //方法一：递归
    ArrayList<Integer> arr = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            printListFromTailToHead(listNode.next);
            arr.add(listNode.val);
        }
        return arr;
    }
    */
    
    /*
    // 方法二：使用ArrayList 中有个方法是 add(index,value)
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode tmp = listNode;
        while(tmp!=null){
            list.add(0,tmp.val);
            tmp = tmp.next;
        }
        return list;
    }
    */
    
    // 链表反转法
    // 时间复杂度: O(n)
    // 空间复杂度: O(n)
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> vals = new ArrayList<>();
        ListNode pre = null, cur = listNode, next;
        // 反转链表
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 添加到vals中
        cur = pre;
        while (cur != null) {
            vals.add(cur.val);
            System.out.println(cur.val);
            cur = cur.next;
        }
        return vals;
    }
    
}
发表于 2021-11-30 21:09:15 回复(0)
Python
The_Flash头像 The_Flash
这样做不知道面试官给不给过
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        res = []
        while listNode:
            res.append(listNode.val)
            listNode = listNode.next
        return res[::-1]
发表于 2018-05-28 20:54:18 回复(3)
惨绿青年头像 惨绿青年

Java解法

递归解法

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> res = new ArrayList<>();
    helper(res, listNode);
    return res;
}

private void helper(ArrayList<Integer> res, ListNode head) {
    if (head != null) {
        if (head.next != null) {
            helper(res, head.next);
        }
        res.add(head.val);
    }
}

栈解法

从尾到头，即先进后出，使用栈。注意，JDK推荐使用Deque代替Stack。

public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
    ArrayList<Integer> res = new ArrayList<>();
    Deque<Integer> stack = new ArrayDeque<>();
    while (listNode != null) {
        stack.push(listNode.val);
        listNode = listNode.next;
    }
    while (!stack.isEmpty()) {
        res.add(stack.pop());
    }
    return res;
}
发表于 2017-01-22 22:19:43 回复(4)
Java
科大讯飞内推君~头像 科大讯飞内推君~ 
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();
         while(listNode!=null)
         {
             list.add(0,listNode.val);
             listNode=listNode.next;
         }
        return list;
        
    }
}
定义一个集合，遍历链表，每次都放在集合的第一个，返回集合，但是这样时间复杂度就有点高了
发表于 2021-11-01 09:50:02 回复(0)
C/C++
InitialD_头像 InitialD_ 
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* pHead)
    {
        vector<int> rst;
        while(pHead != nullptr)
        {
            rst.push_back(pHead->val);
            pHead = pHead->next;
        }
        int sz = rst.size();
        for(int i = 0; i < (sz>>1); ++i)
        {
            rst[i] ^= rst[sz-1-i];
            rst[sz-1-i] ^= rst[i];
            rst[i] ^= rst[sz-1-i];
        }
        return rst;
    }
};
直接翻转容器中的数据。
用到了三次异或位运算交换首位对称的元素；也可以用<algorithm>里的reverse(rst.begin(),rst.end());

编辑于 2019-10-05 18:08:47 回复(0)
心灵蚂蚁头像 心灵蚂蚁
#Python
#直接循序打印链表值，加到列表里，最后反转列表的值就行了
#PS：感觉不用反转链表是不是有点对不起这道题出的本意？？
#PPS：递归实现的那位大佬好厉害
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
if listNode is None:
return []
list_1 = []
while listNode.next is not None:
list_1.append(listNode.val)
listNode = listNode.next
list_1.append(listNode.val)
return list_1[::-1]

#反转链表版本
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if listNode is None:
            return []
        p = None
        while listNode is not None:
            q = listNode
            listNode = q.next
            q.next = p
            p = q
            
        list_1 = []
        while p is not None:
            list_1.append(p.val)
            p = p.next
        return list_1


编辑于 2019-01-07 02:16:55 回复(0)
Java
ZeaLot4J头像 ZeaLot4J 


// 不依赖全局变量， 无副作用，Java语法终究是太拖沓

public static ArrayList intListFromTailToHead(ListNode listNode) {  
    if (listNode == null)  
        return new ArrayList();  
    ArrayList ls = printListFromTailToHead(listNode.next);  
    ls.add(listNode.val);  
    return ls;
}

编辑于 2018-08-30 15:07:29 回复(1)
向宇的上铺头像 向宇的上铺 
就地反转 不依靠别的结构
public class Solution {
    
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList list=new ArrayList();
        if(listNode==null) return list;
        ListNode dummy=new ListNode(0);
        dummy.next=listNode;
        ListNode cur=listNode;
        // 链表就地反转
        while(cur.next!=null)
        {
            ListNode temp=cur.next;
            cur.next=temp.next;
            temp.next=dummy.next;
            dummy.next=temp;
        }
        ListNode head=dummy.next;
        while(head!=null)
        {
            list.add(head.val);
            head=head.next;
        }
        
        
        return list;
        
    }
}



利用栈
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList list=new ArrayList();
        if(listNode==null) return list;
        Stack<ListNode> s=new Stack<>();
        while(listNode!=null)
        {
            s.push(listNode);
            listNode=listNode.next;  }
        while(!s.isEmpty())
        {
            list.add(s.pop().val);
        }
        
        return list;
        
    }
}

编辑于 2018-01-16 09:39:18 回复(0)
Java
、✨头像 、✨ 
简单粗暴    
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> al = new ArrayList<>();
            while(listNode!=null)
            {
                al.add(0,listNode.val);
                listNode=listNode.next;
            }
            return al;
    }
发表于 2017-10-24 14:48:24 回复(0)
C/C++
Younger7_Z头像 Younger7_Z
这个题目的意义应该在于考察递归，但是用库函数一下子就能做出来也是……
        vector<int> output;
        while(head != NULL) {
            output.insert(output.begin(), head->val);
            head = head->next;            
        }
        return output;
发表于 2017-05-19 20:52:47 回复(1)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

从尾到头打印链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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