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

208个回答

添加回答
推荐
方法一:链表从尾到头输出,利用递归实现,不使用库函数直接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 回复(59)

欢迎关注我的CSDN博客(有全部代码):
https://mp.csdn.net/postedit/88762095
方法如下:

1.利用栈



import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> temp = new Stack<>();
        ArrayList<Integer> newList = new ArrayList<>();
        ListNode t = listNode;

            while( t != null ){

                temp.push(t.val);
                t = t.next;
            }
            while( !temp.empty() ){
                newList.add(temp.pop());
            }
            return newList;


    }
}

2.利用ArrayList.add(0,int e),不断添加到第一个位置

import java.util.ArrayList;

     class ListNode {
         int val;
         ListNode next = null;

         ListNode(int val) {
             this.val = val;
         }
    }


public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arr=new ArrayList<>();
        ListNode cur=listNode;
        while(cur!=null){
            arr.add(0,cur.val);
            cur=cur.next;
        }
        return arr;
    }

}

3.利用链表递归

import java.util.ArrayList;

public class Solution {
    ArrayList<Integer> arr=new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        print(listNode);
        return arr;
    }
    public void print(ListNode listNode){
        if(listNode==null)return;
        print(listNode.next);
        arr.add(listNode.val);
        return;
    }


}
发表于 2019-03-23 16:00:36 回复(0)
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> arraylist=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            arraylist.add(listNode.val);
        }
        return arraylist;
    }
}
1.首先可以知道的是,这是一个单链表,如果将其想成一个数组,就只需要从最后一个开始输出即可。
2.那么本着从最后一个开始输出的想法,既然不能通过循环来输出这个单链表的话,那么是否可以通过递归呢?
3.事实证明是可以的,那么递归是怎么递归的呢?
4.既然是递归,那么首先要想到栈,想到栈,就要想到压栈,先进后出,那么问题就比较简单了。
5.来看一个简单的例子:1,2,3,4,5;假如单链表里五个结点的值分别是这样的,我们来简单想一想:通过递归,通过栈,来得到反向输出的结果,第一步,将1压栈,跳到下一个结点,然后依次压栈,跳到下一个结点,直到不存在下一个结点,我们开始递归,并将val值存入arraylist当中,最终返回一个arraylist,就是我们想要的结果了。
6.这里解释一个地方,如果到了最后一个结点,判断下一个节点不存在,这时我们并没有给arraylist中存放数据,所以这个时候arraylist还是null,所以当我们第一次存放数据的时候,数据是在这个arraylist当中的第一个位置,也就是[0]位置。
7.这里if语句中的这个
printListFromTailToHead(listNode.next);
我们还可以使用
this.printListFromTailToHead(listNode.next);
但是经过试验,加了this会比不加this慢8ms,所以我在这里使用的时候并没有使用this。如果我没记错的话,递归调用的时候,会自动生成一个栈,每次递归会多用一个栈内存……所以用不用this似乎没有太大影响?【这里表示疑惑,不太清楚】
8.于是通过if语句,判断当前结点是否存在,如果存在,继续调用,如果不存在,则返回当前的arraylist【第一次返回的时候是null】,当开始返回以后,我们就需要将val一个一个的加入到arraylist当中,从而达到倒序输出,或者我称之为反向输出。
发表于 2019-03-21 10:49:24 回复(0)
// 方法一:
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (listNode == null) {
            return list;
        } else {
            while (listNode != null) {
                // 头部插入
                list.add(0, listNode.val);
                // 下移
                listNode = listNode.next;
            }
            return list;
        }
    }

// 方法二:
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (listNode == null) {
            return res;
        } else {
            while (listNode != null) {
                // 取值
                list.add(listNode.val);
                // 下移
                listNode = listNode.next;
            }
            // 数组
            Integer[] a = new Integer[list.size()];
            list.toArray(a);
            for (int i = a.length - 1; i >= 0; i--) {
                res.add(a[i]);
            }
            return res;
        }
    }

以上两种两种实现方法基本一样,方法一是直接使用ArrayList的add方法每次从头部插入实现倒序,方法二是通过数组实现自己的倒序
发表于 2019-03-20 10:49:20 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        if (head == null) {
            return list;
        }
        ListNode prev = null;
        while(head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        while(prev != null) {
            list.add(prev.val);
            prev = prev.next;
        }
       return list;
    }
}
发表于 2019-03-19 16:51:49 回复(0)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        if(listNode==null){
            return list;
        }
        while(true){
            list.add(0,listNode.val);
            if(listNode.next!=null){
                listNode=listNode.next;
            }else{
                break;
            }
        }
        
        return list;
    }
发表于 2019-03-16 18:34:17 回复(0)
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
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;
    }
}
来自一位评论区大佬的递归,绝了~~~

发表于 2019-03-15 20:53:37 回复(0)
使用stack试了半天才发现没有引入Stack包,郁闷
1.当为空的返回特定格式,这个是后台规定
2.创建一个栈,用来存放链表的值
3.当链表本身(切记,是本身,如果是next,则最后一个加不上)不为空,把它放到了栈中,将链表指向下一位
4.取出栈的值,放回到一个list集合中

发表于 2019-03-12 18:55:07 回复(0)
/*
思路:
方法一 反转链表 (在面试时候,如果我们打算修改输入的数据,最好先问问面试官是不是允许修改)
        ListNode head = listNode;
        ListNode prev = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        head = prev;
方法二 利用栈的后进先出特性
单链表的遍历只能从前往后,但是需要从尾往头输出,这不是典型的”先进后出”么,那么我们可以用栈模拟输出
先将链表从头到尾遍历的同时将节点的值压入一个栈中,然后从栈顶开始逐个输出节点的值
*/

/**
*    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) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        while(listNode!=null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.isEmpty())
            list.add(stack.pop());
        return list;
    }
}

发表于 2019-03-12 16:58:45 回复(0)
1、借助堆栈的“先进后出”实现
/**
*    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;
    }
}
2、递归方法实现
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
      // 必须在外部,否则每次递归都重新创建
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode != null) {
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        
        return list;
    }
}

编辑于 2019-03-11 15:06:43 回复(0)
利用ArrayList中的插入函数,可以直接将获取的值插入到第一个位置
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> resultArrayList = new ArrayList<Integer>();         ListNode now = listNode;         while (null != now) {             resultArrayList.add(0, now.val);             now = now.next;         }         return resultArrayList;
    }
}

发表于 2019-03-08 15:52:09 回复(0)
遍历链表,将val存入栈中,利用栈的后进先出,遍历栈
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        Stack<Integer> stack =new Stack<>();
        for(;listNode != null;listNode=listNode.next){
            stack.push(listNode.val);
        }
        while(! stack.isEmpty()){
            arrayList.add(stack.pop());
        }
        return arrayList;
    }
}

发表于 2019-03-06 10:02:20 回复(0)

题目描述

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

解题思路

这一题给一个单向链表,然后你反向打印出来。其实最容易想到的就是两个方案,一个是将这个链表进行反置,然后依次打印即可。一个就是通过栈这个数据结构,先进后出,那么也可以反向打印出来。由于用栈比较简单,但是链表的反置稍微难一点(其实也不难)并且重要,所以本文用反置链表的方式解决。

关于反转链表如何写,其实真的很简单,搞两个指针,比如我这里是precurr,那么pre指向的结点及其之前表示已经反转好了,curr指向的结点及其之后表示还未反转。

初始状态的时候,pre指向null,可以理解为一个都没有反转,curr指向head,此时确实就是从head开始都没有反转嘛。

下面就是循环,也就很容易了,curr要指向pre,那么curr指向的head也就反转成功了。那么就要更新指针。即pre要指向curr指向过的,即headcurr指向的是head下一个元素开始反转。

那么此时就需要先保存一下curr的下一个结点,然后更新,即precurr都往后移动一格。理由如上。

一直到最后,pre指向了最后一个结点,表示最后一个结点以及前面所有的结点都反转好了。此时从pre开始遍历即可,因为pre就是反转之后的head

我的答案

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();

        if(listNode == null){
            return res;
        }

        ListNode pre = null;
        ListNode curr = listNode;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        //pre就是反向链表的头结点
        while(pre != null){
            res.add(pre.val);
            pre = pre.next;
        }

        return res;
    }
}
发表于 2019-03-05 22:09:44 回复(0)
//超级简单的代码
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ListNode dunmmy=listNode;
    ArrayList<Integer> arr=new ArrayList(); while(dunmmy!=null){
       arr.add(0,dunmmy.val);
        dunmmy=dunmmy.next;
    } return arr;
}

发表于 2019-03-03 08:53:15 回复(0)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> ret = new ArrayList<>();
        if(listNode == null)
            return ret;
        ArrayList<Integer> tmp = new ArrayList<>();
        while(listNode.next != null){
            tmp.add(listNode.val);
            listNode = listNode.next;
        }
        tmp.add(listNode.val);
        while(!tmp.isEmpty()){
            ret.add(tmp.get(tmp.size() - 1));
            tmp.remove(tmp.size() - 1);
        }
        return ret;
    }

啰嗦方法
发表于 2019-02-26 22:20:40 回复(0)
/*
思路:
1.将所有结点入栈
2.将栈顶结点弹出,并 add 到 ArrayList 中
3.返回该 ArrayList
*/
public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
    ArrayList<Integer> ans = new ArrayList<Integer>();
    Stack<Integer> S = new Stack<Integer>();
    ListNode p = listNode;
    while(p!=null) {
        S.push(new Integer(p.val));
        p = p.next;
    }
    while(!S.empty()) {
        ans.add(S.pop());
    }
    return ans;
}



 
发表于 2019-02-26 14:42:22 回复(0)
方法一:从尾到头打印,后进先出,利用栈存储
publicclassSolution {
    publicArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = newStack<>();
        while(listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> list = newArrayList<>();
        while(!stack.isEmpty()) { //如果栈不为空 需调用栈的判断是否为空的方法
            list.add(stack.pop());
        }
        returnlist;
    }
}

第二种:利用递归,栈结构的本质就是递归
public class Solution {
    ArrayList<Integer> list = new ArrayList<>(); //要放在成员变量位置,不然每次递归都创建一个xinde
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            if(listNode.next != null)
                printListFromTailToHead(listNode.next); //打印下个节点的值 开始递归了
            list.add(listNode.val);
        }
        return list;
    }
}

编辑于 2019-02-26 09:37:54 回复(0)
使用栈即可完成这个从尾到头遍历的操作。
我是自己用Deque来实现栈,其实可以直接使用ArrayList依次add,然后直接返回
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
import java.util.Deque;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//链表已经创建好,传入的是第一个节点
//可以借助栈来实现从未到头的顺序返回一个ArrayList
//链表的节点依次进栈,当指向最后一个节点进栈之后,开始出栈即可
Deque<ListNode> stack = new LinkedList<ListNode>();
ArrayList<Integer> al = new ArrayList<Integer>();
//入栈
while(listNode!=null){
stack.add(listNode);
listNode = listNode.next;
}
//出栈
while(!stack.isEmpty()){
listNode = stack.remove();
al.add(0,listNode.val);
}
return al;
}
}
编辑于 2019-02-21 14:45:30 回复(0)
public classSolution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> li=newArrayList<Integer>();
for(;listNode!=null;listNode=listNode.next){
li.add(listNode.val);
}
ArrayList<Integer> res=newArrayList<Integer>();
for(inti=li.size()-1;i>=0;i--){
res.add(li.get(i));
}
return res;
}
}
编辑于 2019-01-10 10:20:33 回复(0)

使用栈的结构

package day01;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @Author: Lance
 * @Date: 2019/1/4 12:07
 */
public class Main
{
    public static void main(String[] args)
    {
        System.out.println("hello");
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode)
    {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack();

        while (listNode != null)
        {
            stack.push(listNode.val);
            listNode = listNode.next;
        }

        while (!stack.isEmpty())
        {
            arrayList.add(stack.pop());
        }


        return arrayList;
    }

    public class ListNode
    {
        int val;
        ListNode next = null;

        ListNode(int val)
        {
            this.val = val;
        }
    }
}
发表于 2019-01-04 15:47:00 回复(0)
将单链表反转再依次将值添加进集合

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode newListNode = reverseList(listNode);
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(newListNode != null){
            list.add(new Integer(newListNode.val));
            newListNode = newListNode.next;
        }
        return list;
    }
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

发表于 2019-01-03 20:15:17 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

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