分隔链表
给你一个头结点为 head 的单链表和一个整数 k ,请你设计一个算法将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
这 k 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长度应该大于或等于排在后面的长度。
返回一个由上述 k 部分组成的数组。
示例 1:
输入:head = [1,2,3], k = 5
输出:[[1],[2],[3],[],[]]
解释:
第一个元素 output[0] 为 output[0].val = 1 ,output[0].next = null 。
最后一个元素 output[4] 为 null ,但它作为 ListNode 的字符串表示是 [] 。
1
2
3
4
5
2
3
4
5
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode[]}
*/
var splitListToParts = function(head, k) {
let ans = new Array(k).fill(null);
if (head === null) {
return ans;
}
let list = head;
let size = 1;
while (list.next) {
size++;
list = list.next;
}
if (k >= size) {
let cur = head;
let index = 0;
while (cur !== null) {
let node = cur;
ans[index] = node;
cur = cur.next;
index++;
}
ans.map((item) => (item !== null ? (item.next = null) : null));
return ans;
} else {
let init = Math.floor(size / k);
let remain = size % k;
let arr = new Array(k).fill(init);
for (let i = 0; i < remain; i++) {
arr[i] = arr[i] + 1;
}
let copy = []
let cur = head;
for (let i = 0; i < arr.length; i++) {
let index = 1;
let num = arr[i]
ans[i] = cur
copy.push(arr[i])
while (index <= num) {
cur = cur.next;
index++;
}
}
for(let i = 0; i < copy.length; i++) {
let next = ans[i]
let index = 1
while (index < copy[i]) {
next = next.next;
index++;
}
next.next = null;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/split-linked-list-in-parts