# LeetCode如何k個一組翻轉鏈表
## 目錄
1. [問題描述與示例](#問題描述與示例)
2. [基礎解法思路分析](#基礎解法思路分析)
3. [遞歸解法詳解](#遞歸解法詳解)
4. [迭代解法實現](#迭代解法實現)
5. [邊界條件處理](#邊界條件處理)
6. [復雜度分析與對比](#復雜度分析與對比)
7. [常見錯誤與調試技巧](#常見錯誤與調試技巧)
8. [擴展與變式題目](#擴展與變式題目)
9. [總結與刷題建議](#總結與刷題建議)
---
## 問題描述與示例
### 題目要求
LeetCode第25題要求實現一個函數，將給定的單鏈表按照每k個節點一組進行翻轉。如果鏈表長度不是k的整數倍，最后剩余的節點保持原有順序。
**函數簽名**：
```python
def reverseKGroup(head: ListNode, k: int) -> ListNode:
示例1：
輸入：head = [1,2,3,4,5], k = 2
輸出：[2,1,4,3,5]
示例2：
輸入：head = [1,2,3,4,5], k = 3
輸出：[3,2,1,4,5]
原始鏈表: 1 -> 2 -> 3 -> 4 -> 5, k=2
分段: [1->2], [3->4], [5]
翻轉后: [2->1], [4->3], [5]
連接結果: 2 -> 1 -> 4 -> 3 -> 5
def reverseKGroup(head: ListNode, k: int) -> ListNode:
# 檢查是否有k個節點
curr = head
count = 0
while curr and count < k:
curr = curr.next
count += 1
if count == k:
# 翻轉當前k個節點
reversed_head = reverse(head, k)
# 遞歸處理后續鏈表
head.next = reverseKGroup(curr, k)
return reversed_head
return head
def reverse(head: ListNode, k: int) -> ListNode:
prev, curr = None, head
for _ in range(k):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while (head != null) {
ListNode tail = pre;
// 檢查剩余長度
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) return dummy.next;
}
ListNode nextGroup = tail.next;
ListNode[] reversed = reverse(head, tail);
head = reversed[0];
tail = reversed[1];
// 重新連接
pre.next = head;
tail.next = nextGroup;
// 移動指針
pre = tail;
head = tail.next;
}
return dummy.next;
}
private ListNode[] reverse(ListNode head, ListNode tail) {
ListNode prev = tail.next;
ListNode curr = head;
while (prev != tail) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return new ListNode[]{tail, head};
}
# Case 1: 常規情況
assert reverseKGroup([1,2,3,4,5], 2) == [2,1,4,3,5]
# Case 2: k=1
assert reverseKGroup([1,2,3], 1) == [1,2,3]
# Case 3: 不足k個
assert reverseKGroup([1,2], 3) == [1,2]
def print_list(head):
while head:
print(head.val, end="->")
head = head.next
print("None")
# 推薦的標準翻轉寫法
def reverse(head):
prev = None
while head:
next_node = head.next
head.next = prev
prev = head
head = next_node
return prev
通過系統性地理解鏈表操作和分組處理的思想，可以解決更復雜的鏈表相關問題。建議在實際編寫代碼時，先畫出指針變化的示意圖，再轉化為代碼實現。 “`
注：本文實際約2800字，完整3700字版本需要補充更多代碼示例、復雜度計算的詳細推導過程以及歷史解題方法的比較等內容。如需完整版本可告知具體需要擴展的部分。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
