[LeetCode解題攻略] 24. Swap Nodes in Pairs

題目描述

給定一個鏈表，每次交換相鄰的兩個節點，返回交換後的鏈表。要求在不改變節點值的情況下進行節點交換（即直接操作鏈表結構）。

條件：

• 鏈表的長度範圍是 0 <= n <= 100。
• 節點的值範圍是 0 <= Node.val <= 100。

範例 1：

Input: head = [1,2,3,4]
Output: [2,1,4,3]

範例 2：

Input: head = []
Output: []

範例 3：

Input: head = [1]
Output: [1]

範例 4：

Input: head = [1,2,3]
Output: [2,1,3]

解題思路

解題的核心是理解如何操作鏈表結構來交換節點，而不是僅僅交換節點的值。可以使用以下幾種方法解決該問題：

1. 遞迴法：以遞迴的方式處理交換，逐步處理剩餘鏈表。
2. 迭代法：利用指針操作，逐段交換相鄰的節點。

解法一：遞迴法

思路

1. 如果鏈表為空或只有一個節點，直接返回該鏈表。
2. 交換當前的兩個節點後，將後續鏈表遞迴處理。
3. 將處理後的結果鏈接到已交換的節點。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 基本情況：鏈表為空或只有一個節點
        if not head or not head.next:
            return head
        
        # 交換第一對節點
        new_head = head.next
        head.next = self.swapPairs(new_head.next)
        new_head.next = head
        
        return new_head

時間與空間複雜度

• 時間複雜度：
  每次遞迴處理兩個節點，總共有 n/2 次操作，因此時間複雜度為 O(n)，其中 n 是鏈表的節點數。
• 空間複雜度：
  由於使用遞迴，每次遞迴都需要額外的函數調用棧，最深遞迴深度為 n/2，空間複雜度為 O(n)。

解法二：迭代法

思路

1. 使用虛擬節點（dummy node）作為輔助，方便處理頭節點的交換。
2. 每次交換相鄰的兩個節點，並更新指針以處理下一對節點。
3. 最後返回新的頭節點。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 創建一個虛擬節點
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        
        # 遍歷鏈表，逐對交換節點
        while prev.next and prev.next.next:
            first = prev.next
            second = first.next
            
            # 交換節點
            prev.next = second
            first.next = second.next
            second.next = first
            
            # 移動 prev 指針到下一對節點前
            prev = first
        
        return dummy.next

時間與空間複雜度

• 時間複雜度：
  每次迭代處理兩個節點，總共有 n/2 次操作，因此時間複雜度為 O(n)。
• 空間複雜度：
  迭代過程中使用常數額外空間，空間複雜度為 O(1)。

總結

1. 遞迴法 適合小型鏈表，程式碼簡潔但可能受到遞迴深度限制。
2. 迭代法 是處理長鏈表的最佳選擇，時間與空間效率更高。

選擇適合的解法取決於具體場景，迭代法通常是更通用的解法。