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.
This approach involves two main steps. First, traverse the linked list to determine its length. Then, decide how to split this length evenly across the k parts. Calculate the base size for each part and determine how many parts need an extra node.
The solution first calculates the total length of the linked list. Using this information, it determines the base size that each part should have and how many of the initial parts should receive an extra node due to the remainder from the division of length by k. It then iterates through the linked list, splitting it into the desired parts by adjusting the next pointers appropriately.
Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list parts.
This approach involves iterating through the linked list and modifying the pointers to split the list directly into parts of calculated sizes based on total length and k. It ensures that the list splitting does not require additional passes, combining calculation and splitting in a single traversal.
This C solution simplifies the approach by combining the length calculation and direct list splitting into one step. By iterating and breaking the list dynamically, this technique ensures efficiency in handling the linked list pointers.
Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list pointers.
| Approach | Complexity |
|---|---|
| Calculate Length and Split | Time Complexity: O(n) where n is the length of the linked list. |
| Iterative Splitting with Modification | Time Complexity: O(n) where n is the length of the linked list. |
| 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. |
Split Linked List in Parts - Leetcode 725 - Python • NeetCodeIO • 15,573 views views
Watch 9 more video solutions →Practice Split Linked List in Parts with our built-in code editor and test cases.
Practice on FleetCode