題幹與適用場景
給定單向鏈結串列頭節點 head 和正整數 k。從頭開始，把每個完整的連續 k 節點分組原地反轉； 如果尾端剩餘節點少於 k，維持原有順序。只能重連節點，不能透過交換 value 偽裝成節點反轉。
例如，1 → 2 → 3 → 4 → 5 在 k = 2 時變成 2 → 1 → 4 → 3 → 5；在 k = 3 時變成 3 → 2 → 1 → 4 → 5。假設 1 ≤ k ≤ n ≤ 5000，輸入無環，目標是 O(n) 時間和 O(1) 額外空間。
這道題適合演算法工程、後端、基礎架構及通用軟體工程的程式設計面試。難點不在「會不會反轉鏈結串列」，而在 能否先確認完整分組、保住下一組入口、正確接回前綴與後綴，並說明為什麼不會遺失節點或形成環。
面試官考察點
第一，能否把問題拆成定位邊界、反轉區間、重新連接三個動作。直接從目前節點開始反轉，一旦走到不足 k 的尾端，就很難在不使用額外儲存的情況下恢復原序。強答案會在修改任何指標前先向前檢查 k 個節點。
第二，能否維持清楚的指標角色。groupPrev 位於目前組之前，kth 是完整組的最後一個節點， groupNext 是下一段入口，目前組原本的頭在反轉後會成為尾。每次迴圈結束後，前綴應已完成且可達， groupPrev.next 應指向第一個尚未處理的節點。
第三，能否給出不變量而非只背程式碼。把 prev 初始化為 groupNext，可以讓目前組原本的頭在第一次被改寫時 最終指向後綴；反轉結束只需把前一段接到 kth，組內和後綴的連接已經成立。
第四，複雜度是否與實作一致。每個節點至多被完整組預檢存取一次、被反轉存取一次，所以總時間仍為 O(n)； 演算法只保存固定數量的節點參照，額外空間為 O(1)。遞迴版本即使時間相同，也會使用與組數相關的呼叫堆疊。
回答前需要釐清的問題
- 最後不足
k個節點怎麼處理？ 本題維持原序。有些變體會反轉尾組，兩者輸出不同，必須先確認契約。 - 可以交換節點值嗎？ 不可以；如果節點還帶有身分、外部參照或其他欄位，換值不等於重連節點。
k的合法範圍是什麼？ 本題保證1 ≤ k ≤ n。通用函式仍可對非整數或小於 1 的值明確拋錯。- 輸入可能有環嗎？ 本題假設無環。若可能有環，應先定義拒絕還是處理；否則預檢與主迴圈可能永不結束。
- 是否必須原地完成？ 是。允許
O(k)空間時，堆疊方案更容易撰寫，但不符合本題目標。 - 節點物件能否重用？ 必須重用所有原節點；不能建立一條只複製值的新鏈結串列。
30 秒回答框架
「我會放一個指向 head 的啞節點，並讓 groupPrev 指向目前組之前。每輪先從 groupPrev 向前走 k 步找到 kth；走不到就直接回傳，因為這時還沒有修改尾端。保存 groupNext = kth.next 後， 把 prev 初始化為 groupNext，再把目前組每個節點的 next 逐個反向。這樣原組頭會自動成為指向 groupNext 的新尾。最後令 groupPrev.next = kth，再把 groupPrev 移到原組頭。每個節點最多經歷 一次預檢和一次反轉，所以時間 O(n)、額外空間 O(1)。」
分步深入解答
先建立啞節點。第一組反轉後鏈結串列頭會改變；啞節點讓「把前綴接到新組頭」在第一組和後續組使用同一行， 避免單獨處理頭節點。
每輪必須先完成分組預檢。從 groupPrev 出發恰好移動 k 次，得到 kth。如果途中到達 null， 剩餘節點不足 k，立即回傳 dummy.next。由於預檢期間沒有寫指標，尾端自然維持原序。
實作如下：
class ListNode {
constructor(value, next = null) {
this.value = value
this.next = next
}
}
function reverseKGroup(head, k) {
if (!Number.isInteger(k) || k < 1) {
throw new RangeError('k must be a positive integer')
}
const dummy = new ListNode(0, head)
let groupPrev = dummy
while (true) {
let kth = groupPrev
for (let step = 0; step < k; step += 1) {
kth = kth.next
if (kth === null) {
return dummy.next
}
}
const groupNext = kth.next
let prev = groupNext
let current = groupPrev.next
while (current !== groupNext) {
const nextNode = current.next
current.next = prev
prev = current
current = nextNode
}
const oldGroupHead = groupPrev.next
groupPrev.next = kth
groupPrev = oldGroupHead
}
}以 1 → 2 → 3 → 4 → 5、k = 3 為例。預檢得到 kth = 3，保存 groupNext = 4。 反轉前令 prev = 4，然後依序改寫 1.next = 4、2.next = 1、3.next = 2。此時 3 是新組頭， 1 是新組尾且已連到 4。把啞節點接到 3，再把 groupPrev 移到 1。下一輪預檢無法取得三個節點， 直接回傳，4 → 5 沒有被改動。
迴圈不變量可以寫成三條：迴圈開始時，dummy.next 到 groupPrev 的前綴已按完整分組正確反轉； groupPrev.next 是第一個未處理節點；所有未處理節點仍維持輸入順序且可達。預檢失敗不寫指標，因此不變量直接 推出尾端維持原序。預檢成功時，反轉只改寫目前 k 個節點，groupNext 保住後綴入口；重新連接後，已完成前綴 恰好多一組，不變量恢復。每輪處理 k 個新節點，最終必然終止。
複雜度方面，預檢和反轉各自最多碰觸每個節點一次，總工作量不超過約 2n 次節點存取，因此為 O(n)， 不是 O(nk)。啞節點和指標數量不隨輸入增長，額外空間為 O(1)。
允許額外空間時，可以把一組節點壓入堆疊再彈出，程式碼更直觀但使用 O(k) 空間。遞迴方案可以先確認完整組、 反轉後遞迴處理剩餘部分，呼叫堆疊為 O(n / k)。面試目標明確要求常數空間時，迭代方案更合適；若輸入很小且 重點是快速交付一個易審查版本，堆疊方案也可以作為明確的第一版。
驗證不能只比較值陣列。應先保存原節點參照集合，執行後沿結果鏈結串列走訪：確認沒有環、節點數量不變、參照 集合完全相同，再檢查順序。最少覆蓋空鏈結串列的防禦性案例、單節點、k = 1、n = k、n 可被 k 整除、尾端不足 k、重複值和最大規模。重複值尤其能證明測試不能依賴節點值判斷是否重用了原物件。
高品質示範回答
「我先確認尾端不足 k 個節點維持原序，而且不能交換值。我的迭代狀態只有一個啞節點和幾個參照。 groupPrev 始終指向目前組前一個節點；每輪從它向前走 k 步。如果找不到 kth，我會立刻回傳， 因為尚未修改任何尾端指標。
找到完整組後，我保存 groupNext。反轉時把 prev 初始化成 groupNext，然後從原組頭走到 groupNext 之前，逐一執行標準三指標反轉。這個初始化很關鍵：原組頭變成尾時，它的 next 已經指向下一段。 反轉完成後，kth 是新組頭，我把 groupPrev.next 接到它，再把 groupPrev 移到原組頭。
正確性依賴一個迴圈不變量：已處理前綴始終正確且連通，groupPrev.next 是第一個未處理節點，未處理後綴仍維持 輸入順序。完整組反轉只擴大前綴；不足一組時沒有寫操作，所以尾端原序保留。每個節點最多被預檢和反轉各存取 一次，時間是 O(n)，額外空間是 O(1)。我會用節點身分和無環檢查驗證，而不只比較值。」
常見錯誤
- 未確認完整組就開始反轉 → 尾端不足
k時已破壞原序且難以恢復 → 先唯讀預檢，再寫指標。 - 反轉時令
prev = null→ 目前組會暫時與後綴斷開，容易漏接 → 令prev = groupNext。 - 只連接新組頭 → 原組頭變成的新尾可能沒有連到後綴 → 保留
groupNext，並檢查新尾指向它。 - 反轉後仍把
kth當作下一輪前驅 → 下一輪邊界錯誤 → 把groupPrev移到原組頭。 - 交換節點值 → 節點身分和附加欄位語意被破壞 → 只修改
next。 - 聲稱遞迴額外空間為
O(1)→ 呼叫堆疊隨組數增長 → 迭代版才符合常數額外空間。 - 只測值序列 → 遺失節點、複製節點或成環可能被漏掉 → 同時檢查參照集合、節點數和無環性。
- 把預檢與反轉相乘成
O(nk)→ 忽略每輪處理新的不相交分組 → 按每個節點的總存取次數求和。
追問及應對
追問一：如果最後不足 k 個節點也要反轉呢？
契約改變後，預檢失敗不能直接回傳。可以讓預檢同時得到實際剩餘數量，並對這段剩餘節點執行相同的區間反轉； 或者先求鏈結串列長度，再令每輪組大小為 min(k, remaining)。需要重寫不變量中的終止條件，並增加 n < k 測試。
追問二：如何每隔一組才反轉？
仍按完整 k 節點組預檢，再維護布林標記。需要反轉的組執行原邏輯；跳過的組不改指標，只把 groupPrev 前移 k 次。尾端規則必須再次確認，因為「最後不足一組」是否算一個需要跳過或反轉的組會改變結果。
追問三：如何證明沒有形成環？
局部證明依賴兩個邊界：反轉前保存不屬於目前組的 groupNext；反轉從 prev = groupNext 開始，並在 current === groupNext 時停止。每條被改寫的邊都從目前節點指向已處理的前驅或後綴入口，不會指回仍未處理的 目前組節點。測試層再使用快慢指標檢查無環，並確認走訪節點數等於輸入節點數。
追問四：如果鏈結串列有一億個節點，方案需要改變嗎？
漸進複雜度不變，但需要取消遞迴、避免複製節點，並評估單次長任務的逾時和取消語意。若鏈結串列位於外部儲存 或跨機分片，隨機重連和原子可見性會成為主要問題，單機記憶體鏈結串列演算法不能直接套用；這時應先重新定義 資料布局、交易邊界和可復原檢查點。