Watch 10 video solutions for Split Linked List in Parts, a medium level problem involving Linked List. This walkthrough by NeetCodeIO has 15,573 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.
The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.
The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.
Return an array of the k parts.
Example 1:
Input: head = [1,2,3], k = 5 Output: [[1],[2],[3],[],[]] Explanation: The first element output[0] has output[0].val = 1, output[0].next = null. The last element output[4] is null, but its string representation as a ListNode is [].
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]] Explanation: The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
Constraints:
[0, 1000].0 <= Node.val <= 10001 <= k <= 50Problem Overview: You are given the head of a singly linked list and an integer k. The task is to split the list into k consecutive parts such that the sizes differ by at most one node. Earlier parts must be larger when the nodes cannot be divided evenly. Each part should remain a valid linked list after splitting.
Approach 1: Calculate Length and Split (O(n) time, O(1) space)
Start by traversing the list once to compute its total length n. The base size of each part becomes n / k, and the first n % k parts receive one extra node. Iterate through the list again and detach segments accordingly. For each part, move a pointer partSize steps, keep track of the previous node, and set prev.next = null to terminate that sublist.
This method works because you know the exact size of every part before performing the split. It requires only two linear passes over the list and constant extra memory. The technique relies heavily on pointer manipulation, which is a fundamental pattern when working with linked list problems.
Approach 2: Iterative Splitting with Modification (O(n) time, O(1) space)
This variation also begins by determining the total length of the list. Instead of computing all sizes up front, the algorithm dynamically adjusts the size of each segment while iterating. Track the remaining nodes and remaining parts. For each step, calculate the current part size using remainingNodes / remainingParts and distribute an extra node when necessary.
Traverse exactly that many nodes, detach the segment, and update counters for the remaining list. This approach modifies the list progressively and avoids storing intermediate sizes in an array. It still performs a single pass for length and another for splitting, keeping the runtime O(n) with constant extra space.
Both strategies rely on careful pointer updates and controlled traversal. Problems like this appear frequently when manipulating list structure, especially in tasks involving segmentation, partitioning, or re-linking nodes within a linked list.
Recommended for interviews: The length calculation approach is the one most interviewers expect. It clearly demonstrates that you can derive part sizes mathematically using n / k and n % k, then apply precise pointer manipulation to split the list. Showing the reasoning behind equal distribution first demonstrates problem understanding, while the clean O(n) implementation shows practical coding skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Calculate Length and Split | O(n) | O(1) | Best general solution. Easy to reason about part sizes using n/k and remainder distribution. |
| Iterative Splitting with Modification | O(n) | O(1) | Useful when computing sizes dynamically while traversing and modifying the list. |