首页 > 试题广场 > 从尾到头打印链表
[编程题]从尾到头打印链表
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

1566个回答

添加回答
推荐
方法一:链表从尾到头输出,利
   查看全部
编辑于 2015-06-18 16:53:34 回复(50)
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 回复(166)
方法一:借助堆栈的“后进先出”实现
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack=new Stack<Integer>();
        while(listNode!=null){
            stack.push(listNode.val);
            listNode=listNode.next;     
        }
        
        ArrayList<Integer> list=new ArrayList<Integer>();
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}


方法二:借助递归实现(递归的本质还是使用了堆栈结构)
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        
        ListNode pNode=listNode;
        if(pNode!=null){
            if(pNode.next!=null){
                list=printListFromTailToHead(pNode.next);
            }
            list.add(pNode.val);
        }
        
        return list;
    }
}

发表于 2015-05-30 19:56:54 回复(31)
啊, Javascript 没人权啦
/*function ListNode(x) {
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head) {
    // write code here
    var res = [], pNode = head;
    while (pNode != null) {
        res.unshift(pNode.val);
        pNode = pNode.next;
    }
    return res;
}
编辑于 2017-09-20 12:29:04 回复(9)
C++版,递归
class Solution {
 public:
  vector<int> dev;
  vector<int>& printListFromTailToHead(struct ListNode* head) {
    if(head!=NULL) {
      if(head->next!=NULL) {
        dev=printListFromTailToHead(head->next);
      }
      dev.push_back(head->val);
    }
    return dev;
  }
};

编辑于 2017-05-11 00:29:35 回复(15)

python版递归法,只有3行代码

# -*- 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  
    if listNode is None:  
        return []  
    return self.printListFromTailToHead(listNode.next) + [listNode.val]
编辑于 2017-12-24 22:29:56 回复(11)
用反向迭代器就好了
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> v;
                       
        ListNode *p = head;
        while (p != nullptr) {
           v.push_back(p->val);
           p = p->next;
        }
        //反向迭代器创建临时对象
        return vector<int>(v.rbegin(), v.rend());
    }
};

发表于 2016-08-01 11:18:51 回复(13)
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        while(listNode != null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        
        Collections.reverse(list);//使用Collections的reverse方法,直接将list反转
        return list;
    }
}

发表于 2016-09-14 13:56:30 回复(15)
# -*- 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 回复(11)
最佳代码:代码思路借助栈,遍历的时候入栈,由于数据结构中栈的特点是先进后出,所以遍历的过程中压栈,推栈,完了弹栈加到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 回复(14)
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
//利用栈的逆序输出特性    	
        stack<int> stack;
        vector<int> vector;
        struct ListNode *p = head;
        if (head != NULL) {
        	stack.push(p->val);
            while((p=p->next) != NULL) {
            	stack.push(p->val);
        	}
            while(!stack.empty()) {
                vector.push_back(stack.top());
                stack.pop();
        	}
        }
        return vector;
    }
        
};

发表于 2015-10-16 10:57:59 回复(9)
有三种思路,第一就是利用栈先入后出的特性完成,第二就是存下来然后进行数组翻转。
第三是利用递归。

栈思路:
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> value;
        ListNode *p=NULL;
        p=head;
        stack<int> stk;
        while(p!=NULL){
            stk.push(p->val);
            p=p->next;
        }
        while(!stk.empty()){
            value.push_back(stk.top());
            stk.pop();
        }
        return value;
    }
};


数组翻转:数组翻转可以用C++自带的函数,也可以自己实现

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> value;
        ListNode *p=NULL;
        p=head;
        while(p!=NULL){
            value.push_back(p->val);
            p=p->next;
        }
        //reverse(value.begin(),value.end()); //C++自带的翻转函数
        int temp=0;
        int i=0,j=value.size()-1;
        while(i<j){
            temp=value[i];    //也可以用swap函数,swap(value[i],value[j]);
            value[i]=value[j];
            value[j]=temp;
            i++;
            j--;
        }
        return value;
    }
};

递归思路:

class Solution {
public:
    vector<int> value;
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p=NULL;
        p=head;
        if(p!=NULL){
            if(p->next!=NULL){
                printListFromTailToHead(p->next);
            }
            value.push_back(p->val);
        }
        return value;
    }
};


编辑于 2018-03-01 16:14:12 回复(1)
感觉大家的代码都有点长,我就直接一个循环解决!
vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> v;
        while(head != NULL)
        {
            v.insert(v.begin(),head->val);
            head = head->next;
        }
        return v;
    }

发表于 2015-08-22 20:51:35 回复(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)

上面的回答基本都是用java或者c实现的,是欺负我javascript没人吗?
这道题实现起来比较简单,就是链表的逆序打印。

/*function ListNode(x){
    this.val = x;        // 节点的数据域
    this.next = null;    // 节点指针域,通过this.next使指针后移
}*/
function printListFromTailToHead(head)
{
    var arr = [];    // 创建一个空数组,将每个节点存放哎数组中
    if(!head) {        // 判断链表是否为空
        return arr;
    }
    while(head) {
        arr.unshift(head.val);    // 使用unshift()方法,将当前节点放到数组的开头
        head = head.next;    // 指针后移
    }

    return arr;    
}
发表于 2017-05-25 23:03:00 回复(2)
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 回复(3)
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)
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)
# 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 回复(3)
有点忘了 链表是啥了。。。
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 回复(0)

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)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

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

  • 公司地址:北京市朝阳区大屯路东金泉时代3-808北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号