題目

3217. Delete Nodes From Linked List Present in Array
難度: 中等偏易

題意

給定一串連鏈接head及一整數k。平均斷開串連鏈結，較長的串聯鏈結要在前面。
範例1:
Input:
linked-list: 1->2->3
K = 5
Output:
[[1], [2], [3], [], []]

範例2:
Input:
linked-list: 1->2->3->4->5->6->7->8->9->10
k = 3
Output:
[[1->2->3->4],[5->6->7],[8->9->10]]

思路

1. 先求出head的長度
2. 平均分攤長度給k個分段
3. 若有剩餘的長度，則從頭開始分配1長度，直到分完為止

實作

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        ListNode* curr = head;
        int count = 0;
        while(curr)
        {
            count++;
            curr = curr->next;
        }

        int part_size = count / k;
        int remain = count - k * part_size;
        vector<ListNode*> res(k);
        curr = head;
        for(int i = 0; i < k; i++)
        {
            res[i] = curr;
            int move = part_size;
            if(remain > 0)
            {
                move++;
                remain--;
            }
            for(int j = 0; j < move; j++)
            {
                ListNode* next_node = curr->next;
                if(j == move - 1)
                    curr->next = nullptr;
                curr = next_node;
            }
        }

        return res;
    }
};

分析

若串連鏈結head長度為N
時間複雜度: O(N)，總共遍歷兩次O(2N)=O(N)
空間複雜度: O(1)

結果