iT邦幫忙

2023 iThome 鐵人賽

DAY 6
0
自我挑戰組

leetcode題目分享系列 第 6

[Day 6] 725. Split Linked List in Parts

  • 分享至 

  • xImage
  •  

-先將分割的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;
    }
};

上一篇
[Day 5] 138. Copy List with Random Pointer
下一篇
[Day 7] 92. Reverse Linked List II
系列文
leetcode題目分享30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言