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 <= 50The key idea in #725 Split Linked List in Parts is to divide a linked list into k consecutive parts that are as equal in size as possible. Start by traversing the list to determine its total length. Once the length is known, compute the base size of each part using integer division and determine how many parts should receive one extra node.
Next, iterate through the linked list and carefully detach segments to form the required parts. The first few segments may contain one additional node if the list length is not perfectly divisible by k. Maintaining pointers while splitting ensures each part remains a valid linked list.
This approach ensures that nodes are distributed evenly while preserving their original order. Since the algorithm primarily involves counting nodes and splitting the list once, the process is efficient. The overall time complexity is O(n), and the extra space used (excluding the output array of parts) is O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Count Length + Greedy Split | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
If there are N nodes in the list, and k parts, then every part has N/k elements, except the first N%k parts have an extra one.
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.
Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list parts.
1class ListNode:
2 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6This Python solution follows the same logic: it calculates the length of the linked list, decides on the split sizes for each part, and uses list indexing to store the result. Python’s handling of list operations and iterations makes the code concise.
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.
Time Complexity: O(n) where n is the length of the linked list.
Space Complexity: O(k) for storing the resulting list pointers.
1 public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode[] SplitListToParts(ListNode root, int k) {
ListNode[] parts = new ListNode[k];
int length = 0;
ListNode node = root;
while (node != null) {
length++;
node = node.next;
}
int partSize = length / k, extraNodes = length % k;
node = root;
for (int i = 0; i < k && node != null; i++) {
parts[i] = node;
int currentSize = partSize + (i < extraNodes);
for (int j = 1; j < currentSize; j++) {
node = node.next;
}
if (node != null) {
ListNode nextPart = node.next;
node.next = null;
node = nextPart;
}
}
return parts;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of linked list partitioning and splitting problems are common in technical interviews at companies like FAANG. They test understanding of pointer manipulation, traversal, and handling edge cases in linked lists.
A singly linked list is the primary data structure used in this problem. The solution relies on pointer manipulation to detach segments of the list and store the resulting parts in an array or list structure.
The optimal approach first counts the total number of nodes in the linked list and then determines the base size of each of the k parts. The first few parts receive one extra node if the list size is not perfectly divisible by k. This allows the list to be split efficiently in a single traversal after counting.
Important edge cases include when the number of parts k is greater than the number of nodes, when the list is empty, and when the nodes cannot be divided evenly. Handling these ensures the first parts are slightly larger while later parts may be null.
This C# implementation efficiently traverses the list once, dividing it by correctly shifting the next pointers. It employs simple logic to determine where to make the cuts, avoiding further passes.