校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 链表算法
题目

把链表分隔成 k 部分,每部分的长度都应该尽可能相同,排在前面的长度应该大于等于后面的

解答

思路:首先遍历链表得到有效数字的个数,再求出分成k份的余数和每一份的均长,前面的部分长度加1直到余数为零。这样是为了保证长度尽可能相同的同时排在前面的长度大于后面的,例如将长度为5的链表分成三份,余2,每一份长度为1,将余下的加到前面,即[ [1+1], [1+1], [1] ]。

class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
int len = 0;
ListNode cur = root;
//遍历得出链表的有效数字
while(cur != null){
cur = cur.next;
len++;
}
//求出余数
int mod = len%k;
//等分的长度
int size =len/k;
ListNode [] res = new ListNode[k];
cur = root;

for(int i = 0; i < k && cur !=null; i++){
res[i] = cur;
int cursize = size + (mod-- > 0? 1:0);
for(int j = 0; j < cursize - 1; j++){
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return res;
}
}


C 0条回复 评论

帖子还没人回复快来抢沙发