第三题 从尾到头打印链表

题目:

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

一、方法一

1、分析

listNode 是链表，只能从头遍历到尾，但是输出却要求从尾到头，这是典型的”先进后出”，我们可以想到栈！
ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值
所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置，最后输出 listNode 即可得到逆序链表

2、代码一

public class Solution {
    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;
    }
}

3、代码二(my)

脱了裤子放屁

ListNode node = listNode;
        int count = 0;
        int k;
        while(listNode!=null)
        {
            count++;
            listNode = listNode.next;
        }
        k = count-1;
        ArrayList<Integer> arrlist = new ArrayList<Integer>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0;i<count;i++)
        {
            arrlist.add(i,(Integer) node.val);
            node = node.next;
        }
        for(int i = 0;i<count;i++)
        {
            int m = arrlist.get(k--);
            arr.add(m);
        }
        return arr;

二、方法二

1、分析

递归实现

2、代码

import java.util.*;
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;
    }
}

三、方法三

1、分析

利用栈实现

2、代码

链接：https://www.nowcoder.com/questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035?answerType=1&f=discussion
来源：牛客网
public ArrayList 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.pop());
    }
    return list;
}