题目描述
给你一个头结点为 head 的单链表和一个整数 k ,请你设计一个算法将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
这 k 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长度应该大于或等于排在后面的长度。
返回一个由上述 k 部分组成的数组。
输入样例
3
1 2 3
5
输出样例
head-->1-->tail
head-->2-->tail
head-->3-->tail
head-->tail
head-->tail
分析
采用贪心的思想:
如果元素个数小于分组个数,那么就把前面的组各放一个,后面都留空。
如果元素个数多于分组个数,那么就取余数,前面余数个组里面的元素比后面多1即可。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* root, int k) {
vector<ListNode*> ans(k);
if(!root) return ans;
//填充本函数完成功能
int tot=0;
auto p=root;
//求链表总长
while(p){
tot++;
p=p->next;
}
//若元素数小于组数
if(tot<=k)
{
int idx=0;
while(root)
{
auto p=new ListNode(root->val);
ans[idx]=p;
idx++;
root=root->next;
}
}
else{
//若元素数大于组数,每组有partlen个元素,有more组的元素个数为partlen+1
int partlen=tot/k;
int more=tot%k;
int idx=0,partidx=1,thislen;
while(root)
{
if(more>0) thislen=partlen+1;
else thislen=partlen;
auto tmp=new ListNode(-1),q=tmp;
for(int i=0;i<thislen;i++)
{
auto p=new ListNode(root->val);
q->next=p;
q=p;
root=root->next;
}
if(partidx<thislen) more--;
ans[idx]=tmp->next;
idx++;
}
}
return ans;
}
};