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

题目描述

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

值得注意的是我们接收的参数是链表的第一个节点，我们也可以看到链表的定义。

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

我的方法

首先我想的是可以把这个链表反转，然后再按顺序输出其中的值：

class Solution {
    public int[] reversePrint(ListNode head) {
        
        ListNode now = head.next;
        ListNode pre = head;
        
        int count = 1;
        
        while(now != null){
            ListNode nowNext = now.next;
            now.next = pre;
            pre = now;
            now = nowNext;
            count++;
        }
        
        int[] res = new int[count];
        int count2 = 0;
        
        while (pre != null){
            
            res[count2] = pre.val;
            pre = pre.next;
        }

        return res;
    }

然后发现我这种方式超时了，很尴尬…

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

方法优化

后来我发现，我不需要改变链表的结构就能实现输出整个数组：

class Solution {
    public int[] reversePrint(ListNode head) {
        
        ListNode test = head;
        int count = 0;
        while(test != null){
            count++;
            test = test.next;
        }

        int[] res = new int[count];
        

        ListNode test2 = head;

        while(count > 0){
            res[count-1] = test2.val;
            
            test2 = test2.next;
            count--;
        }
        return res;
    }
}

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

这两个方法的不同之处在于是否改变链表的结构。

官方方法

因为这个操作与栈的性质先进后出很相像。所以使用了栈来实现：

/**
 * 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> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• 时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。
• 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

栈这个类：