Description
給定一個單向鏈結串列的頭節點
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#
核心思路：計算每個部分的長度（基本長度 + 前幾個部分多 1），然後按長度切割串列。
- 總長度 n 分成 k 份：每份基本長度 n / k，前 n % k 份多 1 個
- 遍歷時按計算好的長度逐段切割
Approaches#
⭐1: Calculate and Split#
- 概念: 先計算總長度，再算每份長度（n/k + 是否多 1），依序切割
- 時間複雜度:
O(n + k)- 遍歷串列 + 建立結果陣列 - 空間複雜度:
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 個
- 關鍵技巧: 切割時要先走到段尾再斷開 next，注意 partSize 為 0 時（k > n）直接跳過