06 从尾到头打印链表

Lin2J
2021-07-21 / 0 评论 / 87 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

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

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

方法一

先遍历整个链表,求得链表的长度 $n$,然后创建一个长度 $n$ 的数组 $ans$。倒序遍历数组 $ans$,而链表正序遍历,将链表的值赋值到数组中。

代码:

public int[] reversePrint(ListNode head){
    if(head == null) {
        return new int[0];
    }
    int len = 0;
    ListNode p = head;
    while(p != null) {
        len++;
        p = p.next;
    }
    int[] ans = new int[len];
    for(int i = len-1; i >= 0; i--){
        ans[i] = head.val;
        head = head.next;
    }
    return ans;
}

复杂度分析

  • 时间复杂度$O(N)$:遍历链表和遍历数组的操作均为 $O(1)$ 时间。
  • 空间复杂度$O(N)$:$ans$ 数组需要 $O(N)$ 空间。

方法二

使用辅助栈,借助栈的先进后出的特点,将链表的元素先全部压入栈中,然后再弹出。

代码:

public int[] reversePrint(ListNode head){
    if(head == null) {
        return new int[0];
    }
    Deque<Integer> stack = new LinkedList<>();
    while(head != null) {
        stack.push(head.val);
        head = head.next;
    }
    int[] ans = new int[stack.size()];
    int k = 0;
    while(!stack.isEmpty()){
        ans[k++] = stack.pop();
    }
    return ans;
}

复杂度分析

  • 时间复杂度 $O(N)$:入栈和出栈共使用 $O(N)$ 时间。
  • 空间复杂度 $O(N)$:辅助栈 $stack$ 和 $ans$ 共使用 $O(N)$ 空间。