[数据结构与算法]剑指 Offer 06. 从尾到头打印链表

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

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

示例 1：

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

这个题目只需要借助一个栈就能完成，首先遍历整个链表，将每个节点的值依次压入栈中，最后再将栈中的值依次出栈放入数组，借助栈先入后出的性质很容易实现顺序的反转。

下面举例说明：

首先将第一个节点的值压栈

将第二个节点的值压栈

将第三个节点的值压栈

将栈顶的值出栈，放入数组

将栈顶的值出栈，放入数组

将栈顶的值出栈，放入数组，得到了要求的数组。

注意：

• 考虑边界值，如果给出的head为null，直接返回一个空数组。
• 栈尽量用Deque来实现，而不用Stack，原因如下：

为什么建议使用Deque替代Stack？

而Stack继承自Vector，这表明Stack是线程安全的顺序栈。线程安全必然带来开销，这是很多时候我们不希望看到的；另一方面，Stack是基于数组实现的，在频繁入栈操作时会进行扩容，，而扩容会带来操作效率的降低。官方称：Deque接口及其实现提供了一组更完整和一致的LIFO堆栈操作，应优先于Stack使用。

Deque

Deque是支持在两端插入和删除元素的线性集合。可将其称为"双端队列"，双端队列也可以用作LIFO（后进先出）堆栈。

构造方法：

Deque<Integer> stack = new ArrayDeque<Integer>();

常用方法：

void push(E e )

E pop( )

E peek( )

踩坑记录：

下面这段代码是我第一次写的，由于偷懒 没有额外定义一个变量来记录stack中的元素个数，在循环的时候直接用i<stack.size()作为循环的终止条件，而随着栈中的元素不断出栈，stack.size()是在不断变化的，导致最终的输出结果会比正确的输出结果少值，如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null){return new int[0];}
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode p = head;
        while(p != null){
            stack.push(p.val);
            p = p.next;
        }
        int[] res = new int[stack.size()];
        for(int i=0;i<stack.size();i++){
            res[i] = stack.pop();
        }
        return res;
    }
}

输出结果如下：

输入      [1,3,2]
输出      [2,3,0]
预期结果   [2,3,1]

结论：我们在用栈等数据结构的大小来做循环条件的时候，一定要额外定义一个变量来记录当前值，否则随着栈内元素的变化，这个值是不固定的

改正后代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null){return new int[0];}
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode p = head;
        while(p != null){
            stack.push(p.val);
            p = p.next;
        }
        int size = stack.size();
        int[] res = new int[size];
        for(int i=0;i<size;i++){
            res[i] = stack.pop();
        }
        return res;
    }
}