Eisen 筆記

#206. Reverse Linked List

題目描述

給你一個單向鏈結串列的頭head，反轉整個鏈結串列並回傳。

限制條件

  1. 節點的數量範圍為[0, 5000]。
  2. -5000 <= 節點值 <= 5000

解題思路

單向鏈結串列是無法從當前節點查詢過去節點的，因此我們需要記下前一個節點才能讓當前節點指向過去的節點，同時在把當前節點指向過去節點之前，需要記錄下一個節點的位置，要不然就會失去前往下個節點的座標。 因此我們會需要三個變數，過去節點prev、當前節點curr，下一個節點next。

迭代 Iteration

public class Solution {	
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode prev = null;
		ListNode curr = head;		
        while(curr.next!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        curr.next = prev;
        return curr;
    }
}

複雜度分析：

  • 時間複雜度：花費的時間上取決於節點數量，因此時間複雜度為O(n)。
  • 空間複雜度：空間上沒有增長，因此空間複雜度為O(1)。

遞迴 Recursion

這一題節點數量最多只有5000，因此也可以使用遞迴來處理。
每一個遞迴的函式會都會將下一個函式所回傳的節點的下一個節點位置指向當前節點，完成反轉。
當處理到最後一個節點時，它的下一個節點會指向null，因此我們知道他是最後一個節點，並且把ans指派給他，等函式堆疊完成後，回傳ans作為答案。

public class Solution {	
    ListNode ans;
    public ListNode ReverseList(ListNode head) {
        if(head==null) return head;
        Reverse(head);
        return ans;
    }
    public ListNode Reverse(ListNode head){
        if(head.next == null){
            ans = head;
            return head;
        }
        ListNode tmp = head.next;
        head.next = null;
        Reverse(tmp).next = head;
        return head;
    }
}

複雜度分析：

  • 時間複雜度：花費的時間上取決於節點數量，因此時間複雜度為O(n)。
  • 空間複雜度：空間使用會因為函式堆疊而成長，最多會和節點數量相同，因此空間複雜度為O(n)。

學習重點

  • 鏈結串列 (Linked List)
  • 迭代 (Iteration)
  • 遞迴 (Recursion)
Last Updated:
Contributors: eisen