Solution For Split Linked List In Parts

Problem statement:

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

Each of the linked list parts should be as equal as possible: no two parts 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 parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Solution:

The given problem can be solved by traversing through the linked list and calculating its length. The length of the linked list is divided by the value of k to find the number of nodes to be present in each part. We also find the remaining nodes that are left after all parts have equal nodes.

We then create a new array of k-linked lists and assign each part its respective nodes. We use the remaining variable to assign the remaining nodes to the first k%nodes will get the remaining nodes since we assign nodes in a round-robin fashion starting from the first partition.

Algorithm:

1. Determine the length of the Linked List_list. The length of the linked list is count.
2. Determine the quotient and remainder from count divided by k.
3. Initialize an empty array result with k linked lists.
4. Initialize a pointer current to head.
5. For i = 0 to k-1:
6. Define size as the quotient of the count of the linked list divided by k.
7. If the remainder is greater than 0, subtract 1 from the remaining variable.
8. Add size nodes from current to result[i].
9. Update the current pointer such that it points to the next node of the last node added to the result[i].
10. Decrease remaining by 1 if it is greater than 0.
11. Repeat Step 8-10 until all linked lists have been divided.
12. Return result.

Python Code:

class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def splitListToParts(head: ListNode, k: int):
# initialize count and current variables
count = 0
current = head

# calculate the length of the linked list
while current:
    count += 1
    current = current.next

# calculate size and remaining
size, remaining = divmod(count, k)

# initialize an empty array of k linked lists
result = [None] * k

# set current pointer back to the head
current = head

# assign nodes to each partition
for i in range(k):
    result[i] = current

    # add size nodes to the partition
    for j in range(size + (i < remaining) - 1):
        if current:
            current = current.next

    # store the next node after the partition in the curr variable
    if current:
        curr = current.next

        # break the linked list
        current.next = None
        current = curr

# return result list of partitions
return result

Time Complexity:

The algorithm has a time complexity of O(n), where n is the number of nodes in the Linked List. Traverse the entire Linked List once to find out its length, then once again to divide it into partitions. Both operations have a linear time complexity. The overall time complexity is O(n).

Sapce Complexity:

We allocate k number of linked lists in the result list. Besides, we use additional pointers and variables, and their space usage does not depend on the linked list size or k. The overall space complexity is O(k).

Step by Step Implementation For Split Linked List In Parts

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        // base case
        if (root == null) {
            return new ListNode[k];
        }
        
        // get the length of the list
        int len = 0;
        ListNode curr = root;
        while (curr != null) {
            curr = curr.next;
            len++;
        }
        
        // calculate the size of each sublist
        int sublistSize = len / k;
        int remainder = len % k;
        
        // create an array to store the sublists
        ListNode[] sublists = new ListNode[k];
        
        // initialize the first sublist
        curr = root;
        sublists[0] = curr;
        
        // create the remaining sublists
        for (int i = 1; i < k; i++) {
            // if there is a remainder, add one to the size of the sublist
            int size = sublistSize;
            if (remainder > 0) {
                size++;
                remainder--;
            }
            
            // create the sublist
            for (int j = 0; j < size - 1; j++) {
                curr = curr.next;
            }
            sublists[i] = curr.next;
            curr.next = null;
            curr = sublists[i];
        }
        
        return sublists;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        # Base case
        if not root:
            return [None] * k
        
        # Get the length of the list
        curr, length = root, 0
        while curr:
            curr, length = curr.next, length + 1
        
        # Split the list into k parts
        part_length, longer_parts = divmod(length, k)
        output = [part_length + 1] * longer_parts + [part_length] * (k - longer_parts)
        
        # Split the list
        curr, prev = root, None
        for index, num in enumerate(output):
            output[index] = curr
            for i in range(num):
                prev, curr = curr, curr.next
            if prev:
                prev.next = None
        
        return output

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} root
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function(root, k) {
    // create an array of k elements
    const result = new Array(k).fill(null);
    
    // base case: if root is null, return the array of k elements
    if (!root) {
        return result;
    }
    
    // get the length of the list
    let length = 0;
    let curr = root;
    while (curr) {
        length++;
        curr = curr.next;
    }
    
    // get the number of elements in each sublist
    let num = length / k;
    let rem = length % k;
    
    // create each sublist
    curr = root;
    for (let i = 0; i < k; i++) {
        // create a new list
        const list = new ListNode(null);
        let temp = list;
        
        // add num elements to the sublist
        for (let j = 0; j < num; j++) {
            temp.next = new ListNode(curr.val);
            curr = curr.next;
            temp = temp.next;
        }
        
        // add an extra element to the sublist if there are any remaining elements
        if (rem > 0) {
            temp.next = new ListNode(curr.val);
            curr = curr.next;
            rem--;
        }
        
        // add the sublist to the result array
        result[i] = list.next;
    }
    
    return result;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector splitListToParts(ListNode* root, int k) {
        // Your code here
        vector parts(k, nullptr);
        int len = 0;
        for (ListNode* node = root; node; node = node->next)
            len++;
        int n = len / k, r = len % k; // n : minimum guaranteed part size; r : extra nodes spread to the first r parts;
        ListNode* node = root, *prev = nullptr;
        for (int i = 0; node && i < k; i++, r--) {
            parts[i] = node;
            for (int j = 0; j < n + (r > 0); j++) {
                prev = node;
                node = node->next;
            }
            prev->next = nullptr;
        }
        return parts;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode[] SplitListToParts(ListNode root, int k) {
        // create an array of ListNodes of size k
        ListNode[] parts = new ListNode[k];
        
        // if the input linked list is null, return the array of ListNodes
        if (root == null) {
            return parts;
        }
        
        // get the length of the input linked list
        int length = 0;
        ListNode current = root;
        while (current != null) {
            length++;
            current = current.next;
        }
        
        // calculate the size of each sublist
        int sublistSize = length / k;
        int remainder = length % k;
        
        // create each sublist
        current = root;
        for (int i = 0; i < k; i++) {
            parts[i] = current;
            // if there is a remainder and we are on the first few sublists, add one to the sublist size
            int currentSublistSize = sublistSize + (remainder > 0 ? 1 : 0);
            // reduce the remainder by one, if it is greater than 0
            if (remainder > 0) {
                remainder--;
            }
            // create the sublist by iterating through the current list and setting the next pointer to null after the sublist size is reached
            for (int j = 0; j < currentSublistSize - 1; j++) {
                if (current != null) {
                    current = current.next;
                }
            }
            // if we are not at the end of the list, set the next pointer of the last node in the sublist to null and update the current node to the next node in the list
            if (current != null) {
                ListNode next = current.next;
                current.next = null;
                current = next;
            }
        }
        return parts;
    }
}