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

177个回答

添加回答
推荐
方法一:链表从尾到头输出,利
   查看全部
编辑于 2015-06-18 16:53:34 回复(50)
其实并没有那么麻烦arraylist中有一个方法就是在固定某个位置插入元素,只要我们不断在0的位置插入元素,就能实现倒叙了,
真的没有那么麻烦,不用什么堆栈
真的没有那么麻烦,不用什么堆栈
真的没有那么麻烦,不用什么堆栈
真的没有那么麻烦,不用什么堆栈

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
     ListNode q = listNode;
        ArrayList<Integer> al = new ArrayList<>();
        while(q != null) {
            al.add(0,q.val);
            q = q.next;
        }
        return al;
        }
    
}

发表于 2018-10-19 21:27:59 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        if(listNode==null){
            return array;
        }else{incertNode(array,listNode);
        return array;}
    }
    public static void incertNode(ArrayList<Integer> array ,ListNode listNode ){
         if(listNode.next!=null){
            incertNode(array,listNode.next);
        }
          array.add(listNode.val);
    }
}
直接利用递归进行求解【过程中忘记了空链表的特例,一直报错】

发表于 2018-10-17 09:58:33 回复(0)
// Java
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> newArrayList = new ArrayList<Integer>();
        if (listNode != null){
            newArrayList.addAll(this.printListFromTailToHead(listNode.next));
            newArrayList.add(listNode.val);
        }
        return newArrayList;
    }
}

发表于 2018-10-13 17:52:30 回复(0)
链表从头到尾输出,很容易想起栈,栈的特点就是先进后出。先用一个栈存进来的每一个值,然后list就添加栈pop返回并删除的栈顶元素。
发表于 2018-09-26 21:20:38 回复(0)
1. 栈
首先想到的是后进先出,就用现成的栈结构来做:
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (listNode != null){
            //推入栈
            stack.push(listNode.val);
            //移至下一个节点
            listNode = listNode.next;
        }
        //推出所有元素
        while (!stack.isEmpty()){
            arrayList.add(stack.pop());
        }
        return arrayList;
    }
}

2. 递归
先找到最后一个节点,然后递归添加到 ArrayList:
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;
    }
}
发表于 2018-09-26 18:03:44 回复(0)
方法一:转置链表,缺点是改变了链表原来的结构
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
        ArrayList<Integer> array = new ArrayList<Integer>();
        ListNode pnode = null;
        ListNode nnode = null;
        if(listNode==null)    return array;
        while(listNode!=null){
            nnode = listNode.next;
            listNode.next = pnode;
            pnode = listNode;
            listNode = nnode;
        }
        while(pnode!=null){
            array.add(pnode.val);
            pnode = pnode.next;
        }
        return array;
}

方法二:利用栈先进后出的特点,循环链表将每个数放入栈中,再循环输出栈中元素
注意:如果链表为空{}, 返回的是一个空栈 [] ,而不是 null
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode ==null){
            ArrayList<Integer> arr =newArrayList<Integer>();
            returnarr;
        }
        Stack<Integer> stack =newStack<Integer>();
        while(listNode !=null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> arr =newArrayList<Integer>();
        while(!stack.isEmpty()){
            arr.add(stack.pop());
        }
        returnarr;
    }
	


方法三:利用递归的思想   
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array =newArrayList<Integer>();
        if(listNode!=null){
            if(listNode.next!=null){
                array = printListFromTailToHead(listNode.next);
            }
            array.add(listNode.val);
        }
        return array;
    }




编辑于 2018-09-25 08:40:26 回复(0)
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        while(listNode!=null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.empty()){
            list.add(stack.peek());
            stack.pop();
        }
        return list;
    }
}

发表于 2018-09-21 11:03:07 回复(0)
两种解题思路,第一种依靠栈的“先进后出”性质;第二种利用递归到链表尾,将后面的先放在arraylist里
发表于 2018-09-10 22:22:04 回复(0)
/**
*    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> s = new Stack<>();
        ArrayList<Integer> arr = new ArrayList<>();
        while(listNode != null){
            s.add(listNode.val);
            listNode = listNode.next;
        }
        while(!s.isEmpty()){
            arr.add(s.pop());
        }
        return arr;
    }
}
发表于 2018-09-03 15:28:15 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList list = new ArrayList();
        while(listNode != null){
            ListNode p = null;
            ListNode q = null;
            p = listNode;
            if(listNode.next != null)
                q = listNode.next;
            else{
                list.add(p.val);
                break;
            }
            while(q.next != null){
                p = q;
                q = q.next;
            }
            list.add(q.val);
            p.next = null;
        }
        return list;
    }
}

发表于 2018-08-31 15:49:52 回复(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 回复(0)
提供一个思路:先计算出链表的长度,通过长度创建一个数组,下标从后向前添加链表节点值。
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> result = new ArrayList<Integer>();
        if(listNode == null){
            return result;
        }
        int size = 1;
        ListNode last = listNode;
        while(last.next!=null){
            size++;
            last = last.next;
        }
        last = listNode;
        int[] data = new int[size];
        for(int i=size-1;i>=0;i--){
            data[i] = last.val;
            last = last.next;
        }
        for(int i=0;i<data.length;i++){
            result.add(data[i]);
        }
        return result;
    }
}

发表于 2018-08-28 17:46:08 回复(0)
import java.util.ArrayList;  public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode pre = null;
       ListNode next = null;   ArrayList<Integer> list = new ArrayList<>();  while (listNode != null){
            next = listNode.next;  listNode.next = pre;  pre = listNode;  listNode = next;  } while (pre != null){
            list.add(pre.val);
      pre = pre.next;  }  return list;  }
}
这道题的解题关键在于实现链表逆置,声明前向节点pre,后向节点next,进入循环处理。结束循环的条件为节点为空,循环处理分四步进行:
1、将当前节点的下一节点存至next;
2、将当前节点的前一节点存至新的下一节点;
3、将当前节点存至新的pre;
4、将next作为新的当前节点循环处理。

发表于 2018-08-19 10:50:58 回复(0)

package learn;

/**

  • @author
  • 问题: 输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
  • 时间限制:1秒 空间限制:32768K 热度指数:606662
  • 思路1:使用递归的方式实现,当listNode==null则说明链表遍历到最后了,开始将数据反向添加到ArrayList中;
  • 这里利用了方法进栈后进先出的思想。
  • 思路2:非递归方法实现,直接遍历链表,每遍历一个元素直接添加到ArrayList中,然后实现ArrayList中序列的倒序。
  • 将ArrayList中前n-1个元素直接添加到ArrayList中,此时ArrayList的size变为原来的两倍(少1);
  • 然后将ArrayList前一半的元素直接remove掉。
    */
    import java.util.ArrayList;

class ListNode {
int val;
ListNode next = null;

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

}

public class Program3 {
public static void main(String[] args) {
ListNode ln1 = new ListNode(1);
ListNode ln2 = new ListNode(2);
ListNode ln3 = new ListNode(3);
ListNode ln4 = new ListNode(4);
ln1.next = ln2;
ln2.next = ln3;
ln3.next = ln4;
ListNode ln = null;
ArrayList<Integer> arrayList = printListFromTailToHead(ln1);
if (arrayList != null)
for (Integer integer : arrayList) {
System.out.print(integer + " ");
}
}

public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    if (listNode != null) {
        while (listNode.next != null) {
            arrayList.add(listNode.val);//添加遍历的元素
            if (arrayList.size() > 1) {//只有一个元素时不需要倒序
                //将前n-1个元素添加到ArrayList中;
                int len = arrayList.size() - 1;
                //动态添加元素到ArrayList中时,集合的size会随着改变,所以要将for循环的结束条件定义在外面。
                //即不能写成for (int i = 0; i < arrayList.size() - 1; i++) 
                for (int i = 0; i < len; i++) {
                    arrayList.add(arrayList.get(i));
                }
                //删除ArrayList中前一半元素,其结束条件如上。
                len = arrayList.size() / 2;
                for (int i = 0; i < len; i++) {
                    arrayList.remove(0);
                }
            }
            listNode = listNode.next;
        }
        //将随后一个元素添加到集合中。
        arrayList.add(listNode.val);
        int len = arrayList.size() - 1;
        for (int i = 0; i < len; i++) {
            arrayList.add(arrayList.get(i));
        }
        len = arrayList.size() / 2;
        for (int i = 0; i < len; i++) {
            arrayList.remove(0);
        }

    }
    return arrayList;

}

}

编辑于 2018-08-14 19:09:31 回复(0)
import java.util.ArrayList;

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

发表于 2018-08-13 11:29:03 回复(0)
if(listNode == null)
    return new ArrayList<Integer>();
ArrayList<Integer> list = printListFromTailToHead(listNode.next);
list.add(listNode.val);
return list;

发表于 2018-08-11 21:50:37 回复(0)
 import java.util.ArrayList;


public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> integers = new ArrayList();
        if(listNode == null)
            return integers;
        else    
            integers.add(listNode.val);

        while((listNode = listNode.next) != null ) {
            integers.add(0,listNode.val);
        }
        return integers;
    }
}
发表于 2018-08-10 10:26:15 回复(1)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
         //还是比较标准的思路,先存,在反转,在里面不能用工具类Collections
         //不然更快一点
        ArrayList<Integer> list = new ArrayList();
        ArrayList<Integer> list2 = new ArrayList();
        while(listNode!=null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        for(int i=list.size();i>0;i--){
            list2.add(list.get(i-1));
        }
        return list2;
    }

发表于 2018-08-08 17:20:07 回复(0)
借助堆栈
/**
*    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<>();
        Stack<ListNode> stack = new Stack<>();
        while(listNode!=null){
            stack.push(listNode);
            listNode = listNode.next;
        }
        while(!stack.empty()){
            list.add(stack.pop().val);
        }
        return list;
    }
}

编辑于 2018-08-07 16:38:34 回复(0)

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;
    }
}
记得导包import java.util.Stack
发表于 2018-07-30 18:50:09 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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