Split Linked List In Parts - Leetcode Solution

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).

1