题目
- 给定一个单链表并给定其头结点root,写一个函数实现将其分割为k个连续的链表
- 每一部分链表的长度要求:两个链表部分的长度不能超过1,某些链表可以置位空(null)
- 这些部分链表必须要按照输入链表的顺序,并且前一部分的长度必须大于等于后面部分的链表长度
- 返回一个分段链表头节点组成的数组
- 举例来说给定输入1->2->3->4, k = 5 返回[[1],[2],[3],[4],null]
- 给定root = [1, 2, 3], k = 5,返回[[1],[2],[3],[],[]]
- 给定root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3,返回Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解题思路
- 首先,给定一个k,一个链表,假设链表长度为length,也即是我们要将链表分为k部分,且每两部分的长度不能超过1,那么按照正常的思想我们就是均分呗,那样就都是一样的
- 但是现在问题来了,我们均分之后即是length/k不能整除,也即是存在余数,此时余数remain=length % k, 既然不能超过1那么我们能做的只有取数组的前remain个数,分别将它的节点数再加1就可以完成我们的目标,有点类似于我们有10个硬币放进三个罐子,任意两个罐子之间的差值不能大于1,按照均分每个罐子3个硬币,此时还剩了一个硬币,再按照从头开始排放入第一个罐子形成4,3,3。如果是11个硬币就是形成4,4,3以此类推
- 在我们确定了平均值和average和remain之后就可以开始给数组装填数据了,数组中每个数对应的链表长度都应该是average或者average+1,形成一个数组的遍历
- 在数组遍历内部每次根据所需分段链表长度然后对链表进行遍历,将分段尾节点的next修改为null,head存入数组即可完成内循环,然后整体就完成了。
源代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] result = new ListNode[k];
int count = 0;
ListNode index = root;
while (index != null) {
count++;
index = index.next;
}
int average = count/k;//平均的
int remaining = count % k;//剩余的
index = root;
ListNode head = root;//每一段的头
for (int i = 0; i < k; i++) {
int total = i < remaining ? average + 1 : average;
for (int j = 0; j < total - 1; j++) {
if (index != null) index = index.next;
}
result[i] = head;
ListNode last = index;
if (last != null) {
index = index.next;
head = index;
last.next = null;
} else head = null;
}
return result;
}
}
网友评论