《剑指Offer》从尾到头打印链表

发表于 2023-04-25 更新于 2024-06-02 分类于剑指Offer 阅读次数：

题目：从尾到头打印链表

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

示例 1：

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

链表的结构中只有指向下一个节点的指针，所以从头到尾遍历链表只能得到正序的数组，需要一些办法将顺序翻转。

解法一：使用栈

栈的结构是先入先出，很容易想到用来翻转顺序。可以将正序遍历的链表节点保存到栈里，遍历完成之后再从栈中取出，就能以倒序遍历整个链表了。

public int[] reverseBookList(ListNode head) {
    Deque<Integer> q = new ArrayDeque<>();
    while (head != null) {
        q.push(head.val);
        head = head.next;
    }
    int[] result = new int[q.size()];
    int i = 0;
    while (!q.isEmpty()) {
        result[i++] = q.pop();
    }
    return result;
}

当然，如果只是需要节点的值，可以在栈中只保存数值，节约空间。

时间复杂度O(n) 空间复杂度O(n)

解法二：使用递归

使用递归和栈其实是一样的，但是递归使用的是方法的调用栈，在数据量很大的情况下会导致栈溢出。

public int[] reverseBookList(ListNode head) {
    List<Integer> list = new ArrayList<>();
    if (head != null) {
        reverseBookList(head, list);
    }
    return list.stream().mapToInt(Integer::intValue).toArray();
}

private void reverseBookList(ListNode head, List<Integer> list) {
    if (head != null) {
        reverseBookList(head.next, list);
        list.add(head.val);
    }
}

题目：从尾到头打印链表

解法一：使用栈

解法二：使用递归

相关代码