Problem Description

You are given the head of a singly linked list and an integer k. Your task is to split this linked list into exactly k consecutive parts.

The key requirements are:

1. Equal Distribution: Each part should have approximately equal length. Specifically, no two parts should differ in size by more than 1 node.

2. Order Preservation: The parts must maintain the original order of nodes from the input list. You cannot rearrange nodes.

3. Size Priority: When the list cannot be divided evenly, the earlier parts should be larger. If you have extra nodes after dividing evenly, distribute them to the first few parts.

4. Handling Small Lists: If the linked list has fewer than k nodes, some parts will be empty (null/None).

For example:

• If you have a list with 10 nodes and k = 3, the parts would have sizes [4, 3, 3]
• If you have a list with 5 nodes and k = 3, the parts would have sizes [2, 2, 1]
• If you have a list with 3 nodes and k = 5, the parts would have sizes [1, 1, 1, null, null]

The function should return an array of k elements, where each element is the head of one part of the split linked list. Each part is itself a properly terminated linked list (the last node's next pointer is set to null).

Intuition

To split a linked list into k parts as evenly as possible, we need to figure out how many nodes each part should contain. The natural approach is to think about division.

If we have n nodes total and need k parts, the base size of each part would be n // k (integer division). However, when n is not perfectly divisible by k, we'll have some leftover nodes given by n % k.

Where should these extra nodes go? According to the problem requirements, earlier parts should be larger or equal in size to later parts. This means we should distribute the extra nodes to the first few parts, giving each of them one additional node.

For example, if n = 10 and k = 3:

• Base size: 10 // 3 = 3
• Extra nodes: 10 % 3 = 1
• Part sizes: The first part gets 3 + 1 = 4 nodes, and the remaining two parts get 3 nodes each

This leads us to the key insight: the first (n % k) parts will have size (n // k) + 1, and the remaining parts will have size (n // k).

Once we know the size of each part, the actual splitting becomes straightforward:

1. First, traverse the list once to count the total number of nodes
2. Calculate the base size and number of extra nodes
3. For each part, traverse the appropriate number of nodes
4. Cut the connection between the current part and the next part by setting the last node's next pointer to None
5. Move to the beginning of the next part and repeat

The beauty of this approach is that it handles all edge cases naturally - if n < k, some parts will have size 0 and will remain as None in our result array.

Learn more about Linked List patterns.

Solution Approach

The implementation follows a two-pass approach to split the linked list into k parts.

Step 1: Count the total nodes

First, we traverse the entire linked list to count the total number of nodes n:

n = 0
cur = head
while cur:
    n += 1
    cur = cur.next

Step 2: Calculate part sizes

Using the divmod function, we calculate:

• cnt: the base size of each part (n // k)
• mod: the number of extra nodes (n % k)

cnt, mod = divmod(n, k)

This tells us that the first mod parts will have cnt + 1 nodes, while the remaining parts will have cnt nodes.

Step 3: Initialize the result array

We create an array of size k initialized with None values to store the head of each part:

ans = [None] * k

Step 4: Split the linked list

We iterate k times to create each part:

cur = head
for i in range(k):
    if cur is None:
        break
    ans[i] = cur
    m = cnt + int(i < mod)
    for _ in range(1, m):
        cur = cur.next
    nxt = cur.next
    cur.next = None
    cur = nxt

For each part i:

• We store the current node as the head of this part: ans[i] = cur
• We calculate the size of this part: m = cnt + int(i < mod)
  • If i < mod, this part gets an extra node, so size is cnt + 1
  • Otherwise, size is cnt
• We traverse m - 1 nodes (starting from 1 since we're already at the first node)
• We save the next node before cutting the connection: nxt = cur.next
• We terminate the current part by setting: cur.next = None
• We move to the beginning of the next part: cur = nxt

The if cur is None: break check handles the case where we have fewer than k nodes, ensuring we don't try to process non-existent nodes.

Time and Space Complexity:

• Time: O(n + k) where n is the number of nodes. We traverse the list once to count nodes and once more to split it.
• Space: O(k) for the result array storing the heads of each part.

Example Walkthrough

Let's walk through splitting a linked list 1 -> 2 -> 3 -> 4 -> 5 into k = 3 parts.

Step 1: Count nodes We traverse the list and count n = 5 nodes.

Step 2: Calculate part sizes

• Base size: cnt = 5 // 3 = 1
• Extra nodes: mod = 5 % 3 = 2

This means the first 2 parts get 1 + 1 = 2 nodes each, and the last part gets 1 node.

Step 3: Create result array Initialize ans = [None, None, None]

Step 4: Split the list

Part 0 (i=0):

• Current position: node 1
• Store head: ans[0] = node 1
• Size calculation: m = 1 + 1 = 2 (since 0 < 2)
• Traverse 1 more node to reach node 2
• Save next: nxt = node 3
• Cut connection: node 2.next = None
• Move forward: cur = node 3
• Part 0: 1 -> 2 -> None

Part 1 (i=1):

• Current position: node 3
• Store head: ans[1] = node 3
• Size calculation: m = 1 + 1 = 2 (since 1 < 2)
• Traverse 1 more node to reach node 4
• Save next: nxt = node 5
• Cut connection: node 4.next = None
• Move forward: cur = node 5
• Part 1: 3 -> 4 -> None

Part 2 (i=2):

• Current position: node 5
• Store head: ans[2] = node 5
• Size calculation: m = 1 + 0 = 1 (since 2 ≮ 2)
• No traversal needed (already at the only node)
• Save next: nxt = None
• Cut connection: node 5.next = None (already None)
• Move forward: cur = None
• Part 2: 5 -> None

Final Result: [1->2, 3->4, 5] representing three separate linked lists with sizes [2, 2, 1].

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main phases:

1. First traversal to count the total number of nodes: This takes O(n) time where n is the length of the linked list.
2. Second traversal to split the list into k parts: This also takes O(n) time as we visit each node exactly once to either assign it to a part or disconnect it from the next part.

Since both phases are sequential and each takes O(n) time, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(k)

The space complexity comes from:

• The answer array ans which stores k references to the head nodes of each part: O(k) space
• A few constant extra variables (n, cur, cnt, mod, m, nxt, i): O(1) space

Therefore, the total space complexity is O(k) + O(1) = O(k), where k is the number of parts to split the list into.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Off-by-One Error When Traversing Each Part

The Problem: A frequent mistake is incorrectly handling the loop that traverses to the end of each part. Developers often write:

# INCORRECT - traverses too many nodes
for _ in range(current_part_size):
    current = current.next

This traverses current_part_size nodes forward from the current position, but since we're already at the first node of the part, we end up going one node too far.

Why It Happens: The confusion arises because current already points to the first node of the part when we start processing it. If a part should have 3 nodes and we're already at node 1, we only need to move forward 2 times to reach node 3, not 3 times.

The Solution: Start the loop from 1 instead of 0:

# CORRECT - traverses exactly to the last node of the part
for _ in range(1, current_part_size):
    current = current.next

Pitfall 2: Not Handling Edge Cases with Empty Parts

The Problem: When the linked list has fewer nodes than k, some parts will be empty. Forgetting to check if current is None before processing can lead to AttributeError:

# INCORRECT - will crash if current is None
for part_index in range(k):
    result[part_index] = current  # current might be None
    current_part_size = base_size + (1 if part_index < extra_parts else 0)
    for _ in range(1, current_part_size):
        current = current.next  # AttributeError if current is None!

The Solution: Add a check for None before processing each part:

# CORRECT - safely handles when we run out of nodes
for part_index in range(k):
    if current is None:
        break  # Remaining parts will stay None
    result[part_index] = current
    # ... rest of the logic

Pitfall 3: Forgetting to Disconnect Parts

The Problem: A subtle but critical error is forgetting to set current.next = None after identifying the last node of each part. Without this, all parts would still be connected, and each part would contain all remaining nodes instead of just its allocated portion.

# INCORRECT - parts remain connected
current = head
for part_index in range(k):
    result[part_index] = current
    current_part_size = base_size + (1 if part_index < extra_parts else 0)
    for _ in range(1, current_part_size):
        current = current.next
    current = current.next  # Just moving forward without disconnecting!

The Solution: Always disconnect the current part from the rest before moving forward:

# CORRECT - properly disconnects each part
next_part_head = current.next  # Save the next part's head
current.next = None            # Disconnect current part
current = next_part_head        # Move to next part

Pitfall 4: Integer Division Confusion

The Problem: In some programming languages or Python 2, division might not work as expected:

# Potentially problematic in Python 2 or other languages
base_size = total_length / k  # Might give float instead of int

The Solution: Use divmod() which clearly returns integer quotient and remainder, or use floor division:

# CORRECT - clear integer division
base_size, extra_parts = divmod(total_length, k)
# OR
base_size = total_length // k
extra_parts = total_length % k