MediumLinked List

Split Linked List in Parts

1 approach, code in every language

Given the head of a singly linked list and an integer k, break the list into k consecutive parts whose sizes are as balanced as possible. Any two parts may differ in length by at most one node, and earlier parts must be at least as long as later parts.

Some parts may be empty when k exceeds the number of nodes. Return an array of the k part heads in order, using an empty (null) reference for any empty part.

Example 1

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

Output: [[1],[2],[3],[],[]]

There are only three nodes for five parts, so the first three parts hold one node each and the last two are empty.

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

Ten nodes over three parts gives base size three with one extra, so the first part gets the extra node.

Constraints

The number of nodes is in the range [0, 1000].
0 <= Node.val <= 1000
1 <= k <= 50

Count Then Cut

Compute the length, derive each part's size from base and remainder, then walk the list severing it at each boundary.

Loading animation…

Intuition

Balancing the parts is pure arithmetic: dividing the length by k gives every part a base number of nodes, and the remainder tells us how many parts need one extra. Handing the extra nodes to the earliest parts guarantees earlier parts are never shorter than later ones. Once we know each part's exact size, splitting is just walking that many nodes and cutting the link at the end. Parts that end up with size zero simply record an empty head. No node values move; we only detach next pointers.

Algorithm walkthrough

1Traverse the list once to measure its length.
2Compute base = length / k and extra = length % k; the first extra parts get base + 1 nodes.
3For each of the k parts, remember the current node as that part's head.
4Advance to the last node of the part by stepping partSize - 1 times.
5If the part is non-empty, save the following node, cut by nulling the current next pointer, and move to the saved node.
6Store each part head in the result array and return it after k iterations.

Implementation

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        length = 0
        node = head
        while node:
            length += 1
            node = node.next
        base, extra = divmod(length, k)
        result: List[Optional[ListNode]] = []
        curr = head
        for i in range(k):
            part_head = curr
            part_size = base + (1 if i < extra else 0)
            for _ in range(part_size - 1):
                curr = curr.next
            if part_size > 0:
                next_part = curr.next
                curr.next = None
                curr = next_part
            result.append(part_head)
        return result

Time

O(n + k)

Space

O(k)

One pass measures the list and another distributes it; the output array of k heads is the only extra allocation.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Dividing a Conveyor Into k Parts is our own problem on the technique behind Split Linked List in Parts: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free