LeetCode 725 - Split Linked List in Parts

LeetCode Problem 725

Difficulty: 🟡 Medium
Topics: Linked List

Solution

Problem Understanding

The problem gives us the head of a singly linked list and an integer k. We must divide the linked list into exactly k consecutive parts while preserving the original order of nodes.

The important requirement is that the parts should be as evenly sized as possible. This means:

• The difference in size between any two parts can be at most one.
• Earlier parts must be larger than or equal to later parts.

For example, if the linked list has 10 nodes and k = 3, then the ideal distribution is:

• 10 ÷ 3 = 3 nodes per part
• 1 extra node remains

So the first 1 part gets one extra node:

• Part 1 → 4 nodes
• Part 2 → 3 nodes
• Part 3 → 3 nodes

If the linked list has fewer nodes than k, some parts must be null. For example:

• 3 nodes
• k = 5

The split becomes:

• [1]
• [2]
• [3]
• []
• []

The input represents:

• head, the first node of a singly linked list
• k, the number of parts we must produce

The output is an array of k linked list heads, where each entry points to the beginning of one split part.

The constraints are relatively small:

• At most 1000 nodes
• k at most 50

This means even moderately inefficient approaches would still pass, but the problem is fundamentally about correct linked list manipulation and careful size distribution.

Several edge cases are important:

• The list may be empty
• k may be larger than the number of nodes
• The list length may divide evenly by k
• The list length may leave a remainder
• We must properly terminate each split by setting next = None

A naive implementation can easily forget to disconnect parts correctly, causing multiple returned parts to still point into later sections of the original list.

Approaches

Brute Force Approach

A straightforward brute force solution would first copy all linked list nodes into an array. Once the nodes are stored in an indexed structure, we can compute the target sizes for each part and reconnect nodes accordingly.

The process would look like this:

1. Traverse the linked list and store every node in an array.
2. Compute:

• base size = n // k
• extra nodes = n % k

3. Slice the array into groups of the correct sizes.
4. Disconnect each group's tail node from the next group.

This approach works because arrays provide direct indexing, making partitioning easy.

However, this method uses additional memory proportional to the number of nodes. Since the linked list can already be traversed directly, storing all nodes is unnecessary.

Optimal Approach

The optimal solution avoids storing nodes in an auxiliary array.

The key observation is that we only need two pieces of information:

• Total number of nodes
• How many nodes each part should contain

Once we know the total length n, we can determine:

• Each part gets at least n // k nodes
• The first n % k parts get one additional node

After computing these sizes, we traverse the linked list again and cut it into segments of the required lengths.

This works efficiently because:

• Every node is visited only a constant number of times
• No extra storage proportional to n is required
• Linked lists naturally support sequential partitioning

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Stores all nodes in an array before splitting
Optimal	O(n)	O(1)	Computes sizes and splits directly in place

Algorithm Walkthrough

Optimal Algorithm

1. Traverse the linked list once to count the total number of nodes.

We need the total length because the split sizes depend entirely on how many nodes exist overall. 2. Compute the base size for each part.

base_size = total_nodes // k

Every part must contain at least this many nodes. 3. Compute how many extra nodes remain.

extra_nodes = total_nodes % k

These extra nodes are distributed one by one to the earlier parts. 4. Create a result array of size k.

Each element will store the head of one linked list part. 5. Start traversing the linked list again.

For each part:

• Determine its size:

current_size = base_size + 1

if extra nodes are still available, otherwise:

current_size = base_size

6. Record the current node as the head of the current part.

This node becomes the starting point of the split segment. 7. Move forward current_size - 1 times.

This positions us at the tail of the current part. 8. Disconnect the current part from the remaining list.

Save:

next_part = current.next

Then cut:

current.next = None

9. Continue processing the remaining nodes.

Move:

current = next_part

10. Repeat until all k parts are created.

Why it works

The algorithm guarantees correctness because:

• Every node belongs to exactly one part

• Parts are created consecutively in original order

• Each part receives either:

• base_size

• or base_size + 1

• Only the first extra_nodes parts receive the larger size

Therefore:

• Size differences never exceed one
• Earlier parts are never smaller than later parts
• All nodes are included exactly once

Python Solution

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

from typing import List, Optional

class Solution:
    def splitListToParts(
        self,
        head: Optional[ListNode],
        k: int
    ) -> List[Optional[ListNode]]:
        
        # Count total nodes
        total_nodes = 0
        current = head
        
        while current:
            total_nodes += 1
            current = current.next
        
        # Determine base size and extra nodes
        base_size = total_nodes // k
        extra_nodes = total_nodes % k
        
        result = []
        current = head
        
        for i in range(k):
            part_head = current
            current_part_size = base_size
            
            # Earlier parts get one extra node
            if i < extra_nodes:
                current_part_size += 1
            
            # Move to the tail of current part
            for _ in range(current_part_size - 1):
                if current:
                    current = current.next
            
            # Disconnect current part
            if current:
                next_part = current.next
                current.next = None
                current = next_part
            
            result.append(part_head)
        
        return result

The implementation begins by counting the number of nodes in the linked list. This is necessary because the distribution of nodes depends on the total size.

After obtaining the total count, the algorithm computes:

• base_size, the minimum number of nodes every part receives
• extra_nodes, the number of parts that should receive one additional node

The main loop runs exactly k times because we must always return exactly k parts, even if some are empty.

For each iteration:

• part_head stores the start of the current segment
• current_part_size determines how many nodes belong in this part
• The traversal advances to the tail node of that segment
• The tail is disconnected by setting current.next = None

The disconnected segment is appended to the result array.

If there are fewer nodes than k, some iterations naturally produce None parts because current becomes None.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func splitListToParts(head *ListNode, k int) []*ListNode {
    
    // Count total nodes
    totalNodes := 0
    current := head
    
    for current != nil {
        totalNodes++
        current = current.Next
    }
    
    baseSize := totalNodes / k
    extraNodes := totalNodes % k
    
    result := make([]*ListNode, 0, k)
    current = head
    
    for i := 0; i < k; i++ {
        
        partHead := current
        currentPartSize := baseSize
        
        if i < extraNodes {
            currentPartSize++
        }
        
        // Move to tail of current part
        for j := 0; j < currentPartSize-1; j++ {
            if current != nil {
                current = current.Next
            }
        }
        
        // Disconnect current part
        if current != nil {
            nextPart := current.Next
            current.Next = nil
            current = nextPart
        }
        
        result = append(result, partHead)
    }
    
    return result
}

The Go implementation follows the same logic as the Python version.

A few Go specific details are worth noting:

• nil is used instead of None
• Slices are used to store the result
• Integer division automatically truncates toward zero
• Pointer manipulation is explicit through *ListNode

Since the constraints are small, integer overflow is not a concern.

Worked Examples

Example 1

Input:

head = [1,2,3]
k = 5

Step 1: Count Nodes

Node	Count
1	1
2	2
3	3

Total nodes:

n = 3

Step 2: Compute Sizes

base_size = 3 // 5 = 0
extra_nodes = 3 % 5 = 3

This means:

Part Index	Size
0	1
1	1
2	1
3	0
4	0

Step 3: Split

Iteration	Current Part	Remaining List
0	[1]	[2,3]
1	[2]	[3]
2	[3]	[]
3	[]	[]
4	[]	[]

Final result:

[[1],[2],[3],[],[]]

Example 2

Input:

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

Step 1: Count Nodes

n = 10

Step 2: Compute Sizes

base_size = 10 // 3 = 3
extra_nodes = 10 % 3 = 1

So:

Part Index	Size
0	4
1	3
2	3

Step 3: Split

First Part

Take 4 nodes:

[1,2,3,4]

Remaining:

[5,6,7,8,9,10]

Second Part

Take 3 nodes:

[5,6,7]

Remaining:

[8,9,10]

Third Part

Take remaining 3 nodes:

[8,9,10]

Final result:

[[1,2,3,4],[5,6,7],[8,9,10]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count nodes, one pass to split
Space	O(1)	Only constant extra variables are used

The algorithm traverses the linked list twice:

• Once to compute the total length
• Once to split the list into parts

No auxiliary data structures proportional to the input size are used. The returned result array is required output space and is not counted toward auxiliary complexity.

Test Cases

# Helper utilities

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

def build_list(values):
    dummy = ListNode()
    current = dummy
    
    for value in values:
        current.next = ListNode(value)
        current = current.next
    
    return dummy.next

def list_to_array(head):
    result = []
    
    while head:
        result.append(head.val)
        head = head.next
    
    return result

def convert_parts(parts):
    return [list_to_array(part) for part in parts]

# Solution instance
solution = Solution()

# Example 1
head = build_list([1, 2, 3])
result = solution.splitListToParts(head, 5)
assert convert_parts(result) == [[1], [2], [3], [], []]  # fewer nodes than k

# Example 2
head = build_list([1,2,3,4,5,6,7,8,9,10])
result = solution.splitListToParts(head, 3)
assert convert_parts(result) == [
    [1,2,3,4],
    [5,6,7],
    [8,9,10]
]  # uneven split with remainder

# Single node
head = build_list([1])
result = solution.splitListToParts(head, 1)
assert convert_parts(result) == [[1]]  # minimal non-empty case

# Empty list
head = build_list([])
result = solution.splitListToParts(head, 3)
assert convert_parts(result) == [[], [], []]  # all parts empty

# Perfect division
head = build_list([1,2,3,4])
result = solution.splitListToParts(head, 2)
assert convert_parts(result) == [
    [1,2],
    [3,4]
]  # equal-sized parts

# k greater than node count
head = build_list([1,2])
result = solution.splitListToParts(head, 5)
assert convert_parts(result) == [
    [1],
    [2],
    [],
    [],
    []
]  # trailing null parts

# Large remainder distribution
head = build_list([1,2,3,4,5,6,7])
result = solution.splitListToParts(head, 4)
assert convert_parts(result) == [
    [1,2],
    [3,4],
    [5,6],
    [7]
]  # first parts get extras

Test	Why
[1,2,3], k=5	Verifies handling when k exceeds node count
[1..10], k=3	Verifies uneven distribution with remainder
[1], k=1	Smallest non-empty valid input
[], k=3	Ensures empty lists produce null parts
[1,2,3,4], k=2	Tests perfectly even division
[1,2], k=5	Confirms trailing empty parts
[1..7], k=4	Verifies correct remainder allocation

Edge Cases

Empty Linked List

If head is None, the linked list contains zero nodes. This case can easily cause bugs if the implementation assumes at least one node exists.

The algorithm handles this naturally because:

• total_nodes becomes 0
• Every part size becomes 0
• Each iteration appends None

The result correctly contains k empty parts.

More Parts Than Nodes

When k > n, some parts must be empty.

A common mistake is accidentally creating fewer than k parts or incorrectly distributing nodes across later parts.

The implementation solves this by always iterating exactly k times. Once all nodes are exhausted, current becomes None, and the remaining parts are appended as empty lists.

Properly Disconnecting Parts

One subtle bug is forgetting to sever the connection between adjacent parts.

For example:

[1,2,3,4]

If the first part should be [1,2] but we never set:

current.next = None

then the first returned part still points to [3,4].

The implementation explicitly stores the next segment head before disconnecting the current tail node. This guarantees every returned part is an independent linked list segment.