給定一個單向鏈結串列的頭節點
head和一個整數k，將串列分割為k個連續的部分。每個部分的長度盡量相等，前面的部分長度 >= 後面的部分，長度差最多為 1。回傳一個包含 k 個鏈結串列的陣列。
Example:
Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3 Output: [[1,2,3,4],[5,6,7,8],[9,10]]
Intuition
TIP
核心思路：計算每個部分的長度（基本長度 + 前幾個部分多 1），然後按長度切割串列。
- 總長度 n 分成 k 份：每份基本長度 n / k，前 n % k 份多 1 個
- 遍歷時按計算好的長度逐段切割
Approaches
1. Collect Nodes then Split by Index — O(n) / O(n)
- Idea: 把節點全收進陣列，計算每段大小後直接用索引斷尾，省去邊走邊數的指標操作
- Time:
O(n) - Space:
O(n)- 節點陣列
class Solution {
fun splitListToParts(head: ListNode?, k: Int): Array<ListNode?> {
val nodes = ArrayList<ListNode>()
var cur = head
while (cur != null) { nodes.add(cur); cur = cur.next }
val n = nodes.size
val base = n / k
var extra = n % k
val res = arrayOfNulls<ListNode>(k)
var idx = 0
for (i in 0 until k) {
val size = base + if (extra > 0) { extra--; 1 } else 0
if (size == 0) continue
res[i] = nodes[idx]
nodes[idx + size - 1].next = null // 斷開段尾
idx += size
}
return res
}
}⭐ 2. Calculate and Split (in-place, space-saving) — O(n + k) / O(k)
- Idea: 先計算總長度，再算每份長度（n/k + 是否多 1），依序切割
- Time:
O(n + k)- 遍歷串列 + 建立結果陣列 - Space:
O(k)- 結果陣列（不計入額外空間的話是 O(1)）
class Solution {
fun splitListToParts(head: ListNode?, k: Int): Array<ListNode?> {
// 計算長度
var length = 0
var curr = head
while (curr != null) {
length++
curr = curr.next
}
val baseSize = length / k
var extra = length % k // 前 extra 個部分多 1 個節點
val result = Array<ListNode?>(k) { null }
curr = head
for (i in 0 until k) {
result[i] = curr
val partSize = baseSize + if (extra > 0) 1 else 0
if (extra > 0) extra--
// 走到這一段的最後一個節點
for (j in 0 until partSize - 1) {
curr = curr?.next
}
// 斷開
if (curr != null) {
val next = curr.next
curr.next = null
curr = next
}
}
return result
}
}🔑 Takeaways
- Pattern: 均勻分割問題的通用公式：基本大小 = n / k，前 n % k 份多分配 1 個
- Key trick: 切割時要先走到段尾再斷開 next，注意 partSize 為 0 時（k > n）直接跳過