LeetCode 剑指Offer 75道练习题

剑指Offer：从尾到头打印链表

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

示例：

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

限制：

0 <= 链表长度 <= 10000

---

解题思路：

解法一：

从尾到头打印链表，我们不难联想到栈(Stack),因为栈的特点是 先进后出(FILO)。
所以我们通过栈来实现链表的从尾到头打印的功能。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> nodeStack = new Stack<ListNode>();

        ListNode temp = head;
        while (temp != null){
            nodeStack.push(temp);
            temp = temp.next;
        }

        int size = nodeStack.size();
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = nodeStack.pop().val;
        }

        return result;
    }
}

解法二：

通过递归的方式进行遍历。
我们在递归方法执行之后再去向全局集合中添加数据，这样也可以做到将数据从内部开始存储，然后在顺序遍历即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    private static final ArrayList<Integer> LIST = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
        LIST.clear();
        resNode(head);

        int[] result = new int[LIST.size()];
        for (int i = 0; i < LIST.size(); i++) {
            result[i] = LIST.get(i);
        }
        return result;
    }

        public static void resNode(ListNode node) {
        if (node != null) {
            resNode(node.next);
            LIST.add(node.val);
        }
    }
}

---