Split Linked List in Parts

Leetcode Problem:

• Split Linked List in Parts

Summary

• Given a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

Approach

• The approach used is to first store the values of the linked list in a vector
• Then, for each part, create a new linked list with the required number of nodes
• The remaining nodes are then added to the next part.

Complexity

• O(n), where n is the number of nodes in the linked list

Explanation

• The solution starts by storing the values of the linked list in a vector
• This is done to easily access the values of the linked list
• Then, for each part, a new linked list is created with the required number of nodes
• The remaining nodes are then added to the next part
• This process is repeated for each part, until all parts have been created
• The time complexity of the solution is O(n), where n is the number of nodes in the linked list, because each node is visited once
• The space complexity is also O(n), because in the worst case, all nodes are stored in the vector.

Solution Code:

/**
 * 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 splitListToParts(ListNode* head, int k) {
        ListNode* ptr = head;
        vector arr;
        vector ans;
        while(ptr){
            arr.push_back(ptr->val);
            ptr = ptr->next;
        }
        int N = arr.size();
        int more = arr.size() % k;
        int arrIdx = 0;
        for(int i = 0 ; i < k ; i++){
            ListNode* tmp = nullptr;
            ListNode* ptr;
            for(int j = 0; j < N / k; j++){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
            }
            if (more){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
                more--;
            }
            ans.push_back(tmp);
        }

        return ans;
    }
};