Split Linked List in Parts — Even Distribution Explained Step by Step

Problem Statement#

LeetCode 725 — Split Linked List in Parts Difficulty: Medium | Pattern: Length Calculation + Even Distribution

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 differ in size by more than one. Earlier parts should be greater than or equal to later parts in size. Parts occurring earlier in the input list should come first in the output. If there are not enough nodes to fill all k parts, the extra parts should be null.

Constraints:

• Number of nodes: 0 <= n <= 1000
• 0 <= Node.val <= 1000
• 1 <= k <= 50

Example 1:

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

Example 2:

Input:  head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation: 10 nodes / 3 parts = base size 3 with remainder 1.
             Part 1 gets 3 + 1 = 4 nodes. Parts 2 and 3 get 3 nodes each.

Why This Problem Matters#

This problem is a practical test of your ability to translate a real-world distribution problem into clean pointer mechanics. The challenge appears at Amazon and Facebook in the context of load balancing and data partitioning questions — "how would you distribute work evenly across workers?" is a system design echo of exactly this problem.

The mathematical core — how to distribute n items into k buckets where some buckets get one extra — is a pattern that appears in pagination, batch processing, and distributed systems. The formula is always: base_size = n // k, extra = n % k, and the first extra buckets get base_size + 1 items.

What makes this a good interview problem is that the linked list nature adds implementation complexity: you cannot jump to an index, you must walk the list and break connections carefully. Getting the pointer cutting right under time pressure tests real linked list fluency.

Candidates who have only used arrays often produce O(n + k) space solutions by converting to arrays first. The optimal approach manipulates pointers in-place and uses O(k) space only for the output array of part heads.

The Core Insight#

Two key observations drive the solution:

Observation 1: After computing base_size = n // k and extra = n % k, each of the first extra parts gets base_size + 1 nodes and the remaining parts get base_size nodes. This guarantees the "differ by at most 1" constraint automatically.

Observation 2: To build each part, walk size - 1 additional steps from the current head (since the head is already counted), then cut the connection by setting curr.next = null and advancing curr to the first node of the next part.

The only tricky case is when n < k — some parts will have zero nodes and must be filled with null. The algorithm handles this naturally: if curr is already null, we store null for that part head and do no traversal.

Visual Dry Run#

Input: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3

n = 10, k = 3
base_size = 10 // 3 = 3
extra = 10 % 3 = 1
 
Part 0 (i=0 < extra=1): size = 3 + 1 = 4  →  [1, 2, 3, 4]
Part 1 (i=1 >= extra):  size = 3           →  [5, 6, 7]
Part 2 (i=2 >= extra):  size = 3           →  [8, 9, 10]

Pointer trace for Part 0 (size=4):

Solution (Optimal)#

from typing import Optional, List
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def splitListToParts(head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
    # Step 1: Count total nodes
    n = 0
    curr = head
    while curr:
        n += 1
        curr = curr.next
 
    # Step 2: Compute base size and number of larger parts
    base_size, extra = divmod(n, k)
 
    # Step 3: Build each part
    result = []
    curr = head
    for i in range(k):
        part_head = curr  # head of this part (could be None)
        size = base_size + (1 if i < extra else 0)
 
        # Walk size - 1 additional steps
        for _ in range(size - 1):
            if curr:
                curr = curr.next
 
        # Cut the list at this point
        if curr:
            curr.next, curr = None, curr.next
 
        result.append(part_head)
 
    return result

function splitListToParts(head, k) {
    // Step 1: Count total nodes
    let n = 0;
    let curr = head;
    while (curr) {
        n++;
        curr = curr.next;
    }
 
    // Step 2: Compute base size and extra
    const baseSize = Math.floor(n / k);
    const extra = n % k;
 
    // Step 3: Build each part
    const result = [];
    curr = head;
    for (let i = 0; i < k; i++) {
        result.push(curr); // head of this part (may be null)
        const size = baseSize + (i < extra ? 1 : 0);
 
        // Walk size - 1 additional steps
        for (let j = 0; j < size - 1; j++) {
            if (curr) curr = curr.next;
        }
 
        // Cut the list
        if (curr) {
            const next = curr.next;
            curr.next = null;
            curr = next;
        }
    }
 
    return result;
}

Complexity:

Common Mistakes#

1. Walking size steps instead of size - 1: The part head is already counted, so you only need size - 1 additional steps to reach the last node of the part.
2. Not handling n < k: When the list has fewer nodes than parts, base_size is 0 and extra is n. The first n parts get 1 node and the remaining k - n parts get null heads. The code handles this naturally if you check if curr before walking.
3. Forgetting to cut the connection: After locating the last node of each part, you must set curr.next = null to terminate that part. Forgetting this leaves all parts interconnected.
4. Not advancing curr after cutting: After cutting, advance curr to curr.next (captured before setting to null) to continue to the next part.
5. Mutating the list unintentionally: The cut operation modifies next pointers in-place. If the problem required the original list to be preserved, you would need to copy nodes — clarify with the interviewer.

Interview Tips#

• State the math first: "n divided by k gives base size. The remainder tells us how many parts get one extra node. I'll distribute from the front."
• Trace a small example: Walk through [1,2,3,4,5] with k=3 (base=1, extra=2) before coding. This shows your approach is correct.
• Name the cut clearly: Explain that you store the next pointer before nulling it, then set curr to the stored next. This avoids confusion.
• Handle the empty list: If head is null, all parts are null. The code handles this naturally.
• Mention the in-place advantage: The approach is O(k) space (output array only) versus O(n) for an array-conversion approach.

Follow-up Questions#

1. What if you needed to preserve the original list? You would need to deep-copy nodes, increasing space to O(n).
2. What if the parts must be exactly equal (no extras allowed)? Only possible when n is divisible by k. Return an error or empty otherwise.
3. Can you split into k equal-weight parts where weight is node value? This becomes a partition problem — much harder. Discuss greedy vs. DP.
4. LeetCode 328 — Odd Even Linked List: A related problem that splits a list into two interleaved parts without computing lengths first.
5. What if k = 1? The answer is just the original list as-is — your loop runs once with size=n and no cut needed.

Key Takeaways#

• The formula base_size = n // k, extra = n % k distributes n items into k buckets where the first extra buckets get one more item — memorize this as a general distribution pattern.
• Walk size - 1 steps from each part head to find the last node of that part, then cut with curr.next = null.
• Advance curr after each cut before starting the next part.
• When n < k, the remaining parts naturally get null heads since curr becomes null before the loop ends.
• Total time is O(n + k): one pass to count, one pass to split. Space is O(k) for the output array.
• This distribution pattern generalizes to pagination, batch processing, and any load-balancing scenario in system design.