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

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

解题思路一：栈

使用栈，遍历链表时，将每个节点对应的val值存储到栈中

因为栈是一种LIFO的数据结构，我们依次将栈顶元素添加至返回数组res，直至栈清空

返回res

代码

Java

/**
 * 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<Integer> stack = new Stack<>();
        int len = 0;
        while(head != null){
            stack.push(head.val);
            head = head.next;
            len++;
        }
        int[] res = new int[len];
        int i = 0;
        while(!stack.isEmpty()){
            res[i++] = stack.pop();
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(N)

我们需要从头至尾遍历链表，并且将栈清空，相当于遍历了两次链表，时间复杂度为：O(N)

• 空间复杂度：O(N)

我们额外使用了栈这种数据结构来存储链表每个节点值，额外空间复杂度为：O(N)
_

解题思路二：使用列表List

使用一个List列表，在遍历链表时，将链表每个节点的值存储在List中

使用

Collections.reverse(list);

反转列表

使用Java8引入的stream将列表转换成数组

list.stream().mapToInt(Integer::valueOf).toArray();

代码

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        Collections.reverse(list);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}

复杂度分析

• 时间复杂度：O(N)

无论是遍历链表，调用 Collections.reverse() 方法，还是将 list 转化为 int 数组，时间复杂度均为：O(N)

• 空间复杂度：O(N)

我们使用了一个 arraylist 存放链表的 val 值，所以额外空间复杂度为：O(N)
_

解题思路三：反转链表

双指针法反转链表，使用一个变量 size 记录链表的长度，这样是为了能够开辟返回数组，最后遍历反转之后的链表，将每个节点对应的 val 值存储到返回数组中。

代码

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        int size = 0;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
            size++;
        }
        int[] res = new int[size];
        int i = 0;
        while(pre != null){
            res[i++] = pre.val;
            pre = pre.next;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(N)

遍历两次链表，时间复杂度为：O(N)

• 空间复杂度：O(1)

我们在反转链表时，只是用了有限的几个变量，所以额外空间复杂度为：O(1)