Split Linked List in Parts Leetcode Solution

Problem Statement:

Split Linked List in Parts Leetcode Solution – Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two elements should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and elements occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example:

Example 1:

Input: 
head = [1,2,3], k = 5

Output: 
[[1],[2],[3],[],[]]

Explanation:

Example 2:

Input: 
head = [1,2,3,4,5,6,7,8,9,10], k = 3

Output: 
[[1,2,3,4],[5,6,7],[8,9,10]]

Explanation:

Approach:

Idea:

1. First, we calculate the length of the given linked list.
2. Now we calculate the number of parts we need to divide the linked list using length / k and the extra number of nodes remaining after that using length % k. The first left parts will have length / k + 1.
3. We run a loop until the head pointer of the linked list is not null,
   1. In the loop first, we put the head into our result vector.
   2. First, we take the current length equals 1, then we check until the current Length < the number of the Nodes we increase the current length by 1 and go to the next node.
   3. After that, we check if the extra number of nodes remaining > 0 we decrease that number and go to the next node.
   4. The end node will go to point the NULL.
4. Now check until the length of the given linked list < k, then we push NULL to our result vector.
5. Return the result vector.

Code:

C++ code for Split Linked List in Parts:

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        
        int len=0;
        ListNode* temp=head;
        
        while(temp){
            len++;
            temp=temp->next;
        }
        
        int numNodes=len/k; 
        int val=len%k;
        int i=0;
        vector<ListNode*> res;
        temp=head;
        while(temp) {
            res.push_back(temp);
            
            int currLen=1;
            while(currLen<numNodes){
                temp=temp->next;
                currLen++;
            }
            if(val>0 && len>k){
                temp=temp->next;
                val--;
            }
            ListNode* x=temp->next;
            temp->next=NULL;
            temp=x;
        }
        while(len<k) {
            res.push_back(NULL);
            len++;
        }
        return res;
    }
};

Java code for Split Linked List in Parts:

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode temp = head;
        int len = 0;
        while (temp != null) {
            temp = temp.next;
            len++;
        }

        int numNodes = len / k;
        int val = len % k;

        ListNode[] res = new ListNode[k];
        temp = head;
        for (int i = 0; i < k; ++i) {
            ListNode h = temp;
            for (int j = 0; j < numNodes + (i < val ? 1 : 0) - 1; ++j) {
                if (temp != null) temp = temp.next;
            }
            if (temp != null) {
                ListNode prev = temp;
                temp = temp.next;
                prev.next = null;
            }
            res[i] = h;
        }
        return res;
    }
}

Complexity Analysis for Split Linked List in Parts Leetcode Solution:

Time Complexity:

Time complexity will be O(N+k), where N is the number of nodes in the given list. If k is large, it could still require creating many new empty lists.

Space Complexity:

Space complexity will be O(k) as the additional space is used to store the result.