首页 > 试题广场 >

从尾到头打印链表

[编程题]从尾到头打印链表
  • 热度指数:1694578 时间限制: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,点此查看相关信息
l两种方法:
1. 反转链表法
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vec;
        ListNode *p,*q,*r;
        
        /*反转链表*/
        q=head;
        p=nullptr;
        while(q!=nullptr){
            r=q->next;
            q->next=p;
            p=q;
            q=r;
        }
        while(p!=nullptr){
            vec.push_back(p->val);
            p=p->next;
        }
        
        return vec;
    }
};

2. 递归法
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vec,tem;
        
        if(head==nullptr)
            return vec;
        vec.insert(vec.begin(),head->val);
        if(head->next!=nullptr){
            tem=printListFromTailToHead(head->next);
        if(tem.size()>0)
            vec.insert(vec.begin(),tem.begin(),tem.end());
        }
        
        return vec;
    }
};
发表于 2017-08-20 22:18:51 回复(0)
更多回答
推荐
方法一:链表从尾到头输出,利用递归实现,不使用库函数直接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 递归超简洁版本
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)
# 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)
# -*- 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)
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)
有反转思想,我们就可以试着用栈来处理。
先将所有节点的值压入栈中。
再从栈中弹出。
就可以达到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)
有点忘了 链表是啥了。。。
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)
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)
/**
*    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)
这样做不知道面试官给不给过
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)
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)
简洁的JavaScript:
function printListFromTailToHead(head)
{
    // write code here
    let arr = [];
    while(head){
        arr.unshift(head.val);
        head = head.next;
    }
    return arr;
}


发表于 2021-09-27 18:15:53 回复(0)
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语法终究是太拖沓
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)
简单粗暴    
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)