-先將分割的size算好
-再創數個小linked-list把curr數到的部分丟進去
-extra的部分要一次扣一個,扣到沒有為止。
-for迴圈內是屬於複製linked-list的基本方式
ref:https://leetcode.com/problems/split-linked-list-in-parts/solutions/4007605/99-10-easy-linked-list/?envType=daily-question&envId=2023-09-06
/**
* 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* head, int k) {
int len = 0;
ListNode* curr = head;
while(curr){
len++;
curr = curr->next;
}
vector<ListNode*> part;
int base = len / k;
int extra = len % k;
curr = head;
for(int i = 1; i <= k; i++){
int part_size = base + (extra > 0);
ListNode *part_head = NULL, *part_tail = NULL;
for(int j = 0; j < part_size; j++){
if(!part_head){
part_head = part_tail = curr;
}
else{
part_tail->next = curr;
part_tail = part_tail->next;
}
if(curr){
curr = curr->next;
}
}
if(part_tail){
part_tail->next = NULL;
}
part.push_back(part_head);
extra = max(extra - 1, 0);
}
return part;
}
};