解題說明
Split Linked List in Parts
題目描述：給定一個單向鏈結串列的頭節點和整數 k，將鏈結串列分割成 k 個連續的部分。每個部分的長度盡可能相等，且前面的部分長度不小於後面的部分。若不能均分，前幾個部分各多一個節點。若節點數少於 k，不足的部分為空。
解題思路：
- 先遍歷一次計算串列總長度
n。 - 每個部分的基本長度為
n / k，前n % k個部分各多分配一個節點。 - 再次遍歷串列，按照計算好的長度分割：對每個部分，走到末尾後斷開鏈結。
C++ 解法
複雜度分析
時間複雜度：O(n + k) — 第一次遍歷計算長度 O(n)，第二次遍歷分割 O(n)，初始化結果陣列 O(k)。
空間複雜度：O(k) — 結果陣列的大小。分割操作本身是原地進行的。
虛擬碼
1. Count total length n of linked list 2. baseLen = n / k, extra = n % k 3. For i from 0 to k-1: a. result[i] = current node b. partLen = baseLen + (1 if i < extra else 0) c. Walk partLen - 1 steps d. Cut: save next pointer, set current.next = null e. Move to saved next pointer 4. Return result
其他解法
一次遍歷法：用快慢指標或預先計算來合併長度計算和分割過程。但由於必須先知道總長才能決定每部分的長度，通常仍需兩次遍歷，優化空間有限。
轉陣列再分割：先將串列轉為陣列，分割後再轉回串列。時間 O(n)，空間 O(n)。邏輯簡單但浪費空間，不如原地分割高效。
延伸思考
- 如果輸入是雙向鏈結串列，分割操作會有何不同？
- 如果要求後面的部分比前面的部分多一個節點（而非前面多），需要怎麼調整？
- 能否在不知道串列總長的情況下完成分割？（提示：考慮兩次遍歷是否可以避免）