Split Linked List in Parts
Medium · Linked Lists · Linked List
Problem
Given the head of a singly linked list and an integer k, cut the list into exactly k consecutive parts and return them as a list of k heads.
- The sizes of any two parts differ by at most one.
- Earlier parts are at least as long as later parts.
- The parts keep the original order, and together they hold every node.
When k is larger than the number of nodes, the trailing parts are empty (None).
from_list([1,2,3]) builds a list and to_list(head) reads one back; the tests compare to_list of every part.
Examples
Input: head = [1,2,3,4,5,6,7], k = 3 Output: [[1,2,3],[4,5],[6,7]]
Seven nodes give sizes 3, 2 and 2, with the larger part first.
Input: head = [1,2], k = 4 Output: [[1],[2],[],[]]
Only two nodes exist, so the last two parts are empty.
Input: head = [1,2,3,4,5,6], k = 2 Output: [[1,2,3],[4,5,6]]
Two parts of three.
Constraints
- 0 <= number of nodes <= 1000
- 0 <= Node.val <= 1000
- 1 <= k <= 50
Approaches
- Baseline: copy the nodes into an array — time O(n + k), space O(n)
Follow-up
Two passes, the first only to count, keep the extra space at O(1) beyond the output. The use cases put the longer parts last and cut by a fixed part size instead of a fixed number of parts.
Related problems
Start free on Cariara · Coding problems · System design studio
