剑指 Offer 06. 从尾到头打印链表

题目

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

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof

解题思路

方法一

• 反转链表后输出到数组

方法二

• 使用递归：先递归到链表尾，然后添加到数组中，递归终止条件为head == null

方法三

• 使用栈：遍历链表时将值入栈，然后再出栈并添加到数组中

代码

反转链表

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode next = null;
        ListNode cur = null;
        int len = 0;
        while(head != null) {
            len++;
            cur = head;
            head = head.next;
            cur.next = next;
            next = cur;
        }
        int[] res = new int[len];
        int i = 0;
        while(cur != null) {
            res[i] = cur.val;
            cur = cur.next;
            i++;
        }
        return res;
    }
}

递归

class Solution {
    List<Integer> list = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int len = list.size();
        int[] res = new int[len];
        for(int i = 0;i < len;i++)
            res[i] = list.get(i);
        return res;
    }
    public void recur(ListNode head) {
        if(head == null) return;
        recur(head.next);
        list.add(head.val);
    }
}

栈

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while(head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int len = stack.size();
        int[] res = new int[len];
        for(int i = 0;i < len;i++)
            res[i] = stack.pop();
        return res;
    }
}