LeetCode 725: Split Linked List in Parts

Problem Restatement

We are given the head of a singly linked list and an integer k.

We need to split the linked list into k consecutive parts.

The parts must follow these rules:

Return an array of length k, where each item is the head of one part.

Input and Output

The function shape is:

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> list[Optional[ListNode]]:
        ...

Examples

Example 1:

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

There are only 3 nodes but we need 5 parts.

So the result is:

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

The last two parts are empty.

Example 2:

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

There are 10 nodes and 3 parts.

Each part gets at least:

10 // 3 = 3

There is one extra node:

10 % 3 = 1

So the first part gets one extra node.

The result is:

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

First Thought: Convert to an Array

A simple approach is to copy all linked-list values into an array.

Then compute the size of each part and rebuild new linked lists.

This is easy, but it does extra work and creates new nodes.

The problem asks us to split the original linked list, so we can reuse existing nodes by cutting next pointers.

Key Insight

First count the number of nodes.

Let:

n = length of the linked list

Each part should have at least:

base = n // k

nodes.

The number of parts that get one extra node is:

extra = n % k

So:

Then walk through the linked list and cut each part after its required number of nodes.

Algorithm

1. Count the total number of nodes n.
2. Compute:

   base = n // k
   extra = n % k
3. Create an empty result list.
4. Set cur = head.
5. For each part index i from 0 to k - 1:
   • Set part_head = cur.
   • Compute the current part size:

     size = base + 1 if i < extra else base
   • Move cur forward size - 1 times to reach the part tail.
   • Cut the list by setting the tail’s next to None.
   • Move cur to the next part head.
   • Append part_head to the result.
6. Return the result.

Correctness

The algorithm first counts the exact number of nodes n.

The values base = n // k and extra = n % k divide the nodes into k part sizes whose total is exactly n. The first extra parts have size base + 1, and the remaining parts have size base. Therefore no two part sizes differ by more than one, and earlier larger parts come before later smaller parts.

During splitting, the algorithm processes nodes from left to right. For each part, it records the current node as the part head, advances exactly the required number of nodes, and cuts the final node from the rest of the list. This produces a consecutive segment of the original list.

After a part is cut, cur moves to the next node, which is the head of the next part. Thus no node is skipped or reused.

If n < k, then base = 0, so only the first n parts receive one node, and the remaining parts receive size 0, represented by None.

Therefore the algorithm returns exactly k consecutive parts with valid sizes and original node order.

Complexity

Let n be the number of nodes.

The linked-list nodes are reused in place.

Implementation

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

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> list[Optional[ListNode]]:
        n = 0
        cur = head

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

        base = n // k
        extra = n % k

        result = []
        cur = head

        for i in range(k):
            part_head = cur
            size = base + (1 if i < extra else 0)

            for _ in range(size - 1):
                cur = cur.next

            if cur:
                next_part = cur.next
                cur.next = None
                cur = next_part

            result.append(part_head)

        return result

Code Explanation

First, count all nodes:

n = 0
cur = head

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

Then compute the base part size and the number of larger parts:

base = n // k
extra = n % k

Start splitting from the original head:

result = []
cur = head

For each part, save its head:

part_head = cur

Compute this part’s size:

size = base + (1 if i < extra else 0)

Move to the tail of the part:

for _ in range(size - 1):
    cur = cur.next

If the part is non-empty, cut it from the rest of the list:

if cur:
    next_part = cur.next
    cur.next = None
    cur = next_part

Finally, store the part head:

result.append(part_head)

Example Walkthrough

Use:

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

Count:

n = 10

Compute:

base = 10 // 3 = 3
extra = 10 % 3 = 1

Part sizes are:

[4, 3, 3]

Split:

Return those three heads.

Testing

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

def build_list(values):
    dummy = ListNode()
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def parts_to_lists(parts):
    return [to_list(part) for part in parts]

def test_split_list_to_parts():
    s = Solution()

    head = build_list([1, 2, 3])
    assert parts_to_lists(s.splitListToParts(head, 5)) == [
        [1],
        [2],
        [3],
        [],
        [],
    ]

    head = build_list([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    assert parts_to_lists(s.splitListToParts(head, 3)) == [
        [1, 2, 3, 4],
        [5, 6, 7],
        [8, 9, 10],
    ]

    head = build_list([])
    assert parts_to_lists(s.splitListToParts(head, 3)) == [
        [],
        [],
        [],
    ]

    head = build_list([1, 2, 3, 4])
    assert parts_to_lists(s.splitListToParts(head, 2)) == [
        [1, 2],
        [3, 4],
    ]

    print("all tests passed")

test_split_list_to_parts()

Test coverage: