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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Split Linked List in Parts

Difficulty: Medium

Problem Description

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

Key Insights

  • The total number of nodes in the linked list can be determined first to calculate the size of each part.
  • Each part can have a size of either length // k or length // k + 1 depending on the remainder when divided.
  • The linked list can be traversed to create the parts, ensuring proper linkage and null assignment where necessary.
  • The order of the parts must be maintained as per the original linked list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list (we traverse the list to split). Space Complexity: O(k), where k is the number of parts we need to return (the array that stores the parts).

Solution

To solve this problem, we will first calculate the total length of the linked list. Based on this length, we can determine the size of each part. We will then traverse the linked list again, splitting it into parts of the calculated sizes while maintaining the order. We will use a simple array to store the heads of the resulting linked list parts.

Code Solutions

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

def splitListToParts(head: ListNode, k: int):
    # Calculate the total length of the linked list
    current = head
    length = 0
    while current:
        length += 1
        current = current.next

    # Determine the size of each part
    part_length = length // k
    remainder = length % k

    # Create an array to hold the parts
    parts = [None] * k
    current = head

    for i in range(k):
        parts[i] = current  # Set the current part's head
        # Determine the size of this part
        current_part_size = part_length + (1 if i < remainder else 0)

        # Traverse to the end of this part
        for j in range(current_part_size - 1):
            if current:
                current = current.next
        
        # Disconnect the current part from the rest of the list
        if current:
            next_part_head = current.next
            current.next = None
            current = next_part_head

    return parts
← Back to All Questions