題目描述
給定一個鏈表，每次交換相鄰的兩個節點，返回交換後的鏈表。要求在不改變節點值的情況下進行節點交換（即直接操作鏈表結構）。
條件：
- 鏈表的長度範圍是
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]
解題思路
解題的核心是理解如何操作鏈表結構來交換節點，而不是僅僅交換節點的值。可以使用以下幾種方法解決該問題：
- 遞迴法：以遞迴的方式處理交換，逐步處理剩餘鏈表。
- 迭代法：利用指針操作，逐段交換相鄰的節點。
解法一：遞迴法
思路
- 如果鏈表為空或只有一個節點，直接返回該鏈表。
- 交換當前的兩個節點後，將後續鏈表遞迴處理。
- 將處理後的結果鏈接到已交換的節點。
程式碼
# 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)。
解法二：迭代法
思路
- 使用虛擬節點（dummy node）作為輔助，方便處理頭節點的交換。
- 每次交換相鄰的兩個節點，並更新指針以處理下一對節點。
- 最後返回新的頭節點。
程式碼
# 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)。
總結
- 遞迴法 適合小型鏈表，程式碼簡潔但可能受到遞迴深度限制。
- 迭代法 是處理長鏈表的最佳選擇，時間與空間效率更高。
選擇適合的解法取決於具體場景，迭代法通常是更通用的解法。
