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

题目地址：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

题目主要信息：

• 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值。
• 返回值保存在数组中。

一、栈

注意：用这种方式要求链表有长度限制，否则链表过长可能会导致栈溢出。

解题思路： 按链表从尾到头的顺序返回每个节点的值，符合栈 后进先出 的原则。

具体做法：

• step 1：遍历单链表，将链表的值 push 压入到栈中。

• step 2：依次 pop 弹出栈顶元素，添加到 ArrayList 中。

import java.util.Arrays;
import java.util.Stack;

public class Solution {

    public static void main(String[] args) {
        ListNode listNode_01 = new ListNode(1);  // 头节点
        ListNode listNode_02 = new ListNode(2);
        ListNode listNode_03 = new ListNode(3);
        listNode_01.next = listNode_02;
        listNode_02.next = listNode_03;
        listNode_03.next = null;

        int[] ints = new Solution().reversePrint(listNode_01); // 传入一个头节点

        System.out.println(Arrays.toString(ints));
    }

    // 节点类
    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    // write your code in this method
    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;
    }

}

复杂度分析：

• 时间复杂度是：$O(n)$，入栈和出战都需要 $O(n)$ 的时间复杂度。

• 空间复杂度是：$O(n)$，栈需要 $O(n)$ 的时间复杂度，数组属于必要空间，而不是额外辅助空间。

二、头插法-反转链表（推荐）

单链表的反转，可以参考：http://c.biancheng.net/view/8105.html

解题思路： 所谓头插法，是指在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。

具体做法：

• step 1：遍历链表，获取链表长度。

• step 2：创建返回数组，长度和链表长度一样。

• step 3：遍历原链表，将位于链表头部的节点摘下来，插入新链表 ( 反转链表 ) 的头部。

• step 4：遍历反转后的链表，将链表的值添加到数组中。

import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        ListNode listNode_01 = new ListNode(1);  // 头节点
        ListNode listNode_02 = new ListNode(2);
        ListNode listNode_03 = new ListNode(3);
        listNode_01.next = listNode_02;
        listNode_02.next = listNode_03;
        listNode_03.next = null;

        int[] ints = new Solution().reversePrint(listNode_01); // 传入一个头节点

        System.out.println(Arrays.toString(ints));
    }

    // 节点类
    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public int[] reversePrint(ListNode head) {
        // 获取链表长度
        int len = 0;
        ListNode pHead = head;
        while(pHead != null){
            len++;
            pHead = pHead.next;
        }

        // 创建返回数组，长度和链表长度相等
        int[] res = new int[len];

        // 头插法-反转链表
        ListNode new_head = null;  // 新的反转链表的头节点
        ListNode temp = null;   // 辅助节点
        // 遍历链表
        while(head != null){
            temp = head;
            // 将 head 从链表中移除
            head = head.next;
            // 将 temp 插入到 new_head 的头部
            temp.next = new_head;
            new_head = temp;
        }

        // 遍历反转后的单链表，将链表的值 添加到 数组中
        int i = 0;
        while(new_head != null){
            res[i] = new_head.val;
            i++;
            new_head = new_head.next;
        }

        return res;
    }
}

复杂度分析：

• 时间复杂度是：$O(n)$。获取链表长度的时间复杂度为$O(n)$，反转链表的时间复杂度为$O(n)$，遍历新链表向数组添加元素的时间复杂度为$O(n)$。因此总体时间复杂度为$O(n+n+n)$ = $O(n)$

• 空间复杂度是：$O(1)$，常量级变量，无额外辅助空间。( 数组属于必要空间，而不是额外辅助空间 )

三、反向思维（从数组尾部往前添加元素）（推荐）

解题思路： 打破数组从左往右添加元素的固定思维，我们可以从右往左添加元素，达到一个反序的效果。

具体做法：

• step 1：遍历单链表，统计节点个数。
• step 2：定义一个辅助数组，长度为链表节点数量。
• step 3：遍历单链表，将链表的值从右往左添加到数组中。

import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        ListNode listNode_01 = new ListNode(1);  // 头节点
        ListNode listNode_02 = new ListNode(2);
        ListNode listNode_03 = new ListNode(3);
        listNode_01.next = listNode_02;
        listNode_02.next = listNode_03;
        listNode_03.next = null;

        int[] ints = new Solution().reversePrint(listNode_01); // 传入一个头节点

        System.out.println(Arrays.toString(ints));
    }

    // 节点类
    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    // write your code in this method
    public int[] reversePrint(ListNode head) {
        // 获取链表长度
        int len = 0;
        ListNode pNode = head;
        while(pNode != null){
            len++;
            // 移动指针，指向下一个节点
            pNode = pNode.next;
        }

        // 辅助数组，长度等于链表长度
        int[] res = new int[len];

        int index = len - 1;
        // 遍历单链表，将链表的值从右往左添加到数组中
        while(head != null){
            res[index] = head.val;
            index--;
            // 移动指针，指向下一个链表节点
            head = head.next;
        }

        return res;
    }

}

复杂度分析：

• 时间复杂度是：$O(n)$，两次遍历链表都需要 $O(n)$ 的时间复杂度。

• 空间复杂度是：$O(1)$，常量级变量，无额外辅助空间。( 数组属于必要空间，而不是额外辅助空间 )