題目敘述
Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.
The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.
The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.
Return an array of the k parts.
Example 1:
Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].
Example 2:
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]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
Constraints:
- The number of nodes in the list is in the range
[0, 1000].
0 <= Node.val <= 10001 <= k <= 50
Hint 1:
If there are N nodes in the list, and k parts, then every part has N/k elements, except the first N%k parts have an extra one.
題目翻譯
給定兩個參數，參數 head 是一個 Linked List，和一個參數 k 是一個整數。此題會需要的就是將 head 拆分成 k 個。如果有沒有辦法平分的部分，就從第一組開始分配。例如範例二，沒辦法將 head 平等拆成三份，就將多出來的放到第一個 [1, 2, 3, 4]。
解法解析
這題的解法，會先需要找出餘數，這樣才知道需要另外處理的部分，所以這邊會用一個迴圈來處理大概會是 O(n)。然後再用雙層的迴圈做拆分，第一層迴圈遍歷需要拆分的份數 O(k)，第二層則是遍歷 head，將拆分的結果儲存起來，這邊要特別就是判斷餘數，看是不是有多餘的部分要處理。
Time complexity：O(N + k).
Space complexity：O(k)
程式範例
Python
class Solution:
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
cur = head
for N in range(1001):
if not cur:
break
cur = cur.next
width, remainder = divmod(N, k)
ans = []
cur = head
for i in range(k):
tmp = cur
for _ in range(width + (i < remainder) - 1):
if cur:
cur = cur.next
if cur:
cur.next, cur = None, cur.next
ans.append(tmp)
return ans
JavaScript
var splitListToParts = function (head, k) {
let len = 0;
let cur = head;
while (cur) {
++len;
cur = cur.next;
}
let remainder = 0;
let width = Math.floor(len / k);
if (width === 0) width = 1;
else remainder = len % k;
let result = [];
cur = head;
for (let i = 0; i < k; i++) {
const tmp = cur;
let j = 0;
while (j < width + (i < remainder) - 1) {
if (cur) {
cur = cur.next;
}
j++;
}
if (cur) {
const temp = cur.next;
cur.next = null;
cur = temp;
}
result.push(tmp);
}
return result;
};
Go
func splitListToParts(head *ListNode, k int) []*ListNode {
len := 0
for cur := head; cur != nil; cur = cur.Next {
len++
}
width, remainder := len/k, len%k
ans := make([]*ListNode, k)
cur := head
for i := 0; i < k && cur != nil; i++ {
ans[i] = cur
var rc int
if remainder > 0 {
rc = 1
}
for j := 1; j < width+rc; j++ {
cur = cur.Next
}
remainder--
t := cur.Next
cur.Next = nil
cur = t
}
return ans
}
Swift
class Solution {
func splitListToParts(_ head: ListNode?, _ k: Int) -> [ListNode?] {
var ret = [ListNode?]()
var N = 0
var node = head
while node != nil {
node = node!.next
N += 1
}
var r = N % k, q = N / k
var cur = head
for i in 0..<k {
ret.append(cur)
var size = q + (i < r ? 1 : 0)
var j = 1
while j < size {
cur = cur?.next
j += 1
}
let next = cur?.next
cur?.next = nil
cur = next
}
return ret
}
}
Kotlin
- var next: ListNode? = null
- ```
}
*/
class Solution {
fun splitListToParts(head: ListNode?, k: Int): Array {
val listSize = size(head)
val splitSize = listSize / k
val plusOne = listSize % k
var itr = head
val result = Array<ListNode?>(k) { null }
for (i in 1..k) {
result[i - 1] = itr
itr = run(itr, splitSize - 1 + if (plusOne >= i) 1 else 0)
val next = itr?.next
itr?.next = null
itr = next
}
return result
}
private fun size(head: ListNode?): Int {
var count = 0
var itr = head
while (itr != null) {
itr = itr.next
count++
}
return count
}
private fun run(head: ListNode?, num: Int): ListNode? {
var itr = head
repeat(num) { itr = itr?.next }
return itr
}
}
```