描述

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

0 <= 链表长度 <= 10000

思路1：使用列表，倒序取出

遍历存到列表中，再倒序取出

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode cur = listNode;
        ArrayList temp = new ArrayList();
        while (cur != null) {
            temp.add(cur.val);
            cur = cur.next;
        }
        ArrayList ret = new ArrayList();
        for (int i = temp.size() - 1; i >= 0; i--) {
            ret.add(temp.get(i));
        }
        return ret;
    }
}

思路2：使用栈

使用栈或者LinkedList，每次插入到头部，再从头部取出

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        LinkedList<Integer> list = new LinkedList<>();
        ListNode cur = listNode;
        while(cur != null) {
            list.addFirst(cur.val);
            cur = cur.next;
        }
        ArrayList<Integer> ret = new ArrayList<>();
        while(!list.isEmpty()) {
            ret.add(list.pop());
        }
        return ret;
    }
}

思路3：递归

递归到底部创建数组，出栈时添加

//递归的本质就是栈，先遍历压栈，结束之后再出栈
//    recurse(1) {——递推阶段，压栈
//        recurse(2) {
//            recurse(3) {
//                return;
//            }——回溯阶段，出栈
//        }
//    }
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        recur(listNode);
        return list;
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    public void recur(ListNode node) {
        if(node == null) {
            return;
        }
        recur(node.next);
        list.add(node.val);
    }
}

上面是使用列表，如果要求使用数组，可以在递归结束时初始化大小

class Solution {
    //使用i记录递推次数，递归到底部创建数组，使用j回溯的时候赋值
    private int i = 0;
    private int j = 0;
    private int[] result;

    public int[] printListFromTailToHead(ListNode head) {
        recurse(head);
        return result;
    }

    private void recurse(ListNode node) {
        if (node == null) {
            //递归结束时初始化大小
            result = new int[i];
            return;
        }
        i++;
        recurse(node.next);
        result[j++] = node.val;
    }
}

思路4：反转链表

双指针反转链表，再遍历取出

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