Split Linked List in Parts

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

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