題目描述
給定一個鏈表，將鏈表的節點每 k 個一組進行反轉，並返回修改後的鏈表。如果節點總數不是 k 的倍數，則保留最後剩餘節點的順序。要求在不改變節點值的情況下進行反轉（即直接操作鏈表結構）。
條件：
- 鏈表的長度範圍是
0 <= n <= 5000。 - 節點的值範圍是
0 <= Node.val <= 1000。 1 <= k <= n。
範例 1：
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Explanation: 每 2 個節點一組進行反轉，結果為 [2,1,4,3,5]。
範例 2：
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Explanation: 每 3 個節點一組進行反轉，結果為 [3,2,1,4,5]。
範例 3：
Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]
Explanation: k = 1 時，鏈表保持不變。
範例 4：
Input: head = [1], k = 1
Output: [1]
解題思路
該問題的核心在於分段反轉鏈表。可以通過以下步驟來完成：- 遍歷鏈表，找出每 k 節點的範圍。
- 將這 k 個節點進行反轉，並將反轉後的部分重新鏈接到整體鏈表。
- 處理剩餘不足 k 個的部分，保持原樣。
解法一：模擬分組反轉
思路
- 使用一個指針遍歷整個鏈表，找到每 k 個節點作為一組。
- 每次反轉這一組內的節點，並將其鏈接到已處理的部分。
- 如果剩餘節點不足 k，則不進行反轉。
程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 計算鏈表長度
def getLength(node):
length = 0
while node:
length += 1
node = node.next
return length
# 反轉一段鏈表
def reverseList(start, end):
prev = None
current = start
while current != end:
temp = current.next
current.next = prev
prev = current
current = temp
return prev
# 虛擬節點
dummy = ListNode(0)
dummy.next = head
prev_group = dummy
# 獲取鏈表長度
length = getLength(head)
# 遍歷鏈表，每 k 個為一組進行反轉
while length >= k:
group_start = prev_group.next
group_end = group_start
for _ in range(k - 1):
group_end = group_end.next
next_group = group_end.next
# 反轉當前組
group_end.next = None
prev_group.next = reverseList(group_start, None)
group_start.next = next_group
# 更新指針
prev_group = group_start
length -= k
return dummy.next
時間與空間複雜度
- 時間複雜度：
- 每次反轉操作需要遍歷 k 個節點，總共有
n/k次反轉，因此時間複雜度為 O(n)，其中n是鏈表的節點數。
- 每次反轉操作需要遍歷 k 個節點，總共有
- 空間複雜度：
- 使用了常數額外空間，空間複雜度為 O(1)。
解法二：遞迴法
思路
- 對於前 k 個節點進行反轉。
- 剩下的部分使用遞迴處理，並將反轉後的部分接回已處理的部分。
- 基本情況：如果剩餘節點不足 k，則返回原鏈表。
程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 檢查是否有足夠的節點可以反轉
current = head
count = 0
while current and count < k:
current = current.next
count += 1
if count < k:
return head
# 反轉前 k 個節點
prev = None
current = head
for _ in range(k):
temp = current.next
current.next = prev
prev = current
current = temp
# 遞迴處理剩餘部分
head.next = self.reverseKGroup(current, k)
return prev
時間與空間複雜度
- 時間複雜度：
- 與解法一相同，每次遞迴處理 k 個節點，因此時間複雜度為 O(n)。
- 空間複雜度：
- 使用遞迴函數調用棧，最深遞迴深度為
n/k，因此空間複雜度為 O(n/k)。
- 使用遞迴函數調用棧，最深遞迴深度為
解法三：迭代法
此方法與解法一相似，進行少量優化以提高效率和代碼可讀性。
思路
迭代法的核心在於使用指針遍歷鏈表，逐步反轉每一組 k 個節點，並在反轉完成後重新將每組節點正確地鏈接起來。過程中，保持指針的更新和臨時保存反轉區間的節點信息。
步驟如下：
- 使用一個虛擬節點（dummy node）方便操作頭節點的連接。
- 設置指針追蹤每組需要反轉的起點和終點。
- 反轉 k 個節點，並記錄反轉後的頭尾節點。
- 更新指針以處理下一組節點，直到鏈表中剩餘節點不足 k。
程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 輔助函數：反轉單向鏈表
def reverseList(head):
prev = None
current = head
while current:
temp = current.next
current.next = prev
prev = current
current = temp
return prev, head # 返回新的頭節點和尾節點
# 建立虛擬節點
dummy = ListNode(0)
dummy.next = head
prev_group = dummy # 追蹤每組反轉後的尾節點
while True:
# 找到需要反轉的一組節點
group_start = prev_group.next
group_end = prev_group
for _ in range(k):
group_end = group_end.next
if not group_end:
return dummy.next # 如果不足 k 個節點，直接返回結果
# 保存下一組的起點
next_group = group_end.next
group_end.next = None # 暫時斷開鏈表
# 反轉當前組
reversed_head, reversed_tail = reverseList(group_start)
# 將反轉後的節點接回原鏈表
prev_group.next = reversed_head
reversed_tail.next = next_group
# 更新指針，為下一組做準備
prev_group = reversed_tail
時間與空間複雜度
- 時間複雜度：
- 每次反轉一組 k 個節點需要 O(k)，鏈表總共有 n/k 組，因此時間複雜度為 O(n)。
- 空間複雜度：
- 僅使用了指針進行操作，額外空間為常數，因此空間複雜度為 O(1)。
總結
- 模擬分組反轉 是最直觀的解法，適合初學者。
- 遞迴法 更具可讀性，但遞迴深度可能成為性能瓶頸。
- 針對大規模鏈表，應選擇迭代法以降低空間複雜度。
選擇適合的解法取決於具體場景，對於需要高效處理的應用場景，迭代法更為優秀。
