从尾到头打印链表

从尾到头打印链表

题目描述：

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

解题思路

列表 + 反转法

• 遍历链表的同时，用列表保存其值，然后反转列表即可
• 时间复杂度：O(n)，空间复杂度：O(n)

class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer> l = new ArrayList<>();
        while (head != null) {
            l.add(head.val);
            head = head.next;
        }
        Collections.reverse(l);

        return l.stream().mapToInt(Integer::valueOf).toArray();
}

栈

• 基本操作
• 时间复杂度：O(n)，空间复杂度：O(n)

class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        int count = 0;
        while (head != null) {
            count++;
            stack.push(head.val);
            head = head.next;
        }

        int idx = 0, ans[] = new int[count];
        while (idx < count) {
            ans[idx++] = stack.pop();
        }

        return ans;
}

反转链表法

• 将链表进行反转，然后遍历得到结果，如果需要的话，最后再将链表进行还原
• 时间复杂度：O(n)，空间复杂度：O(1) （不包含返回值 int[] 所占空间）

class Solution {
    int count;
    public int[] reversePrint(ListNode head) {
        head = reverse(null, head, head);
        ListNode cur = head;

        int idx = 0, ans[] = new int[count];
        while (cur != null) {
            ans[idx++] = cur.val;
            cur = cur.next;
        }
        head = reverse(null, head, head);

        return ans;
    }

    private ListNode reverse(ListNode pre, ListNode next, ListNode cur) {
        count = 0;
        while (cur != null) {
            count++;
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

知识点

1. List 调用 toArray(T[]) 方法转换为数组时，这里 T 代表泛型，泛型必须为引用类型。所以不能这样 list.toArray(new int[0])，但可以这样 list.toArray(new int[0][0])，因为 int[] 时引用类型。如果要将 list 转为维度为 (3, 2) 的数组，不需要这样 list.toArray(new int[3][2])，可以但没有必须，使用 list.toArray(new int[0][0]) 执行速度更快。详情看参考链接
2. Java 中一般使用 ArrayDeque 双向队列来模拟栈，而不用 Stack，原因大概有：
   • Stack 继承于 Vector ，是 Java 早期的产物，里面有很多冗余的方法，使用不方便。且被遗弃，JAVA 官方也不推荐使用此类
   • 很多方法都用了 synchronized 修饰符，虽然保证了线程安全，但效率会很低。一般场景下使用 ArrayDeque 即可，如果在需要保证线程安全时，使用 Collections.synchronizedCollection()将其转换为线程安全的即可
3. Collections.reverse(List<?> list) 核心操作：以中心为轴，交换对称的元素

ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
    Object tmp = fwd.next();
    fwd.set(rev.previous());
    rev.set(tmp);
}

参考链接

List (或ArrayList) 转换为int[]数组 终于搞懂了

Java中List, Integer[], int[]的相互转换

You should use toArray(new T[0]) instead of toArray(new T[size]).

Arrays of Wisdom of the Ancients