algoadvance

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 parts should have a size differing by more than one.
• This may lead to some parts being null if there are not enough nodes to divide by k.

Return an array of the k parts.

Example:

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

Constraints:

• The number of nodes in the list is in the range [0, 1000].
• 0 <= Node.val <= 1000
• 1 <= k <= 50

Clarifying Questions

1. Can the input linked list be empty?
   • Yes, the problem constraints allow for this.
2. What should be the return format?
   • A list containing k smaller linked list parts. Each part should be referenced by its head node, with None representing empty parts.
3. How should the linked list parts be ordered?
   • They should be ordered consecutively as they appear in the original linked list.

Strategy

1. Determine Length: First, find the total length of the input linked list.
2. Calculate Sizes: Compute the size of each part. Every part will have at least length//k nodes, except the first length%k parts which will have one extra node each to handle the remainder.
3. Split List: Iterate through the linked list and split it according to these calculated sizes.
4. Create Parts: Using list slicing and pointer manipulations as necessary to create the parts.
5. Return Parts: Collect the sub-linked lists and return them in an array.

Code

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

def splitListToParts(head: ListNode, k: int):
    # Step 1: Calculate the total length of the linked list
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # Step 2: Calculate the size of each part
    part_length = length // k
    remainder = length % k
    
    # Step 3: Split the list
    parts = []
    current = head
    for i in range(k):
        part_head = current
        part_size = part_length + (1 if i < remainder else 0)
        
        # Move the current pointer to the end of the current part
        for j in range(part_size - 1):
            if current:
                current = current.next
        
        # Break the list if needed
        if current:
            temp = current.next
            current.next = None
            current = temp
        
        # Add the current part to the result
        parts.append(part_head)
    
    return parts

Time Complexity

• Calculating Length: O(n), where n is the number of nodes in the list.
• Splitting List: O(n), as we iterate through the list once more to split it into parts.
• Total: O(n), since all operations involve linear scans of the list.

This solution ensures we split the linked list into k parts as evenly as possible in linear time, adhering to the constraints and requirements set by the problem statement.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?