We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split Linked List in Parts

Number: 725

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google, Meta, Amazon, Microsoft, Uber

Problem Description

Given the head of a singly linked list and an integer k, split the linked list into k consecutive parts. The parts should have sizes as equal as possible such that no two parts differ in size by more than one. If the total number of nodes is not divisible by k, the first few parts will have an extra node. The resulting array of parts should maintain the order from the original list and include null for any parts that do not receive nodes.

Key Insights

  • Count the total number of nodes in the linked list.
  • Compute the base size for each part by doing an integer division of total nodes by k.
  • Calculate the extra nodes (using modulus) which will be distributed one per part for the first extra parts.
  • Traverse the linked list, disconnecting sublists based on the computed sizes.
  • If the list is shorter than k, extra parts will be null.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. Space Complexity: O(k), used for storing the resultant list of parts.

Solution

The solution uses a two-pass strategy:

  1. First, traverse the linked list to count the total number of nodes.
  2. Determine the size of each part (base size and extra nodes for the first several parts).
  3. In the second pass, iterate over the list, splitting it into parts based on the computed sizes. For each part, disconnect the sublist after the required number of nodes and add the starting node of that part to the result array. The primary data structure used is the linked list itself, and we manipulate pointers to split it. The algorithm is straightforward and leverages simple arithmetic to distribute nodes as equally as possible.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def splitListToParts(head, k):
    # First pass: calculate the total number of nodes
    total_nodes = 0
    current = head
    while current:
        total_nodes += 1
        current = current.next

    # Determine the base size of each part and the number of extra nodes
    part_size = total_nodes // k
    extra_nodes = total_nodes % k

    # Prepare the output list
    parts = []
    current = head

    # Second pass: split the list into parts
    for i in range(k):
        part_head = current  # head of the current part
        # Calculate the current part's size: base part size plus one extra if available
        current_part_size = part_size + (1 if i < extra_nodes else 0)
        
        # Traverse current part and disconnect it from the rest of the list
        for j in range(current_part_size - 1):
            if current:
                current = current.next
        
        # If current is not None, disconnect current part from the next one
        if current:
            next_part_head = current.next  # store next part's head
            current.next = None  # split the list
            current = next_part_head  # move to the next part
        
        # Append the current part's head (could be None)
        parts.append(part_head)
    return parts
← Back to All Questions