Split Linked List in Parts
Medium · Linked List · Explanation and code example
Iteration
How it works
We can avoid the extra array by working directly with the linked list. First, count the total nodes. Then traverse again, splitting the list into parts by tracking the current node and severing links at the appropriate positions. The first remainder parts each have one more node than the remaining parts.
Steps
- Count the total number of nodes in the list.
- Calculate
base_len = length / kandremainder = length % k. - Traverse the list to create
kparts:- Record the current node as the head of this part.
- Advance
base_len - 1 + (1 if remainder > 0 else 0)steps to reach the tail. - Save
curr.next, setcurr.next = nullto sever, then continue from the saved node. - Decrement
remainderafter each extra-length part.
- Return the array of part heads.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)extra space.O(n)space for the output array.
Things to watch for
Forgetting to Sever the Link Between Parts
After determining where each part ends, you must set the tail node's next pointer to null. Failing to do this leaves the parts still connected, causing the output to contain overlapping or incorrectly sized lists instead of independent segments.
Incorrect Distribution of Extra Nodes
When n % k != 0, the first remainder parts should each have one extra node. A common mistake is distributing extra nodes to the wrong parts (e.g., the last parts instead of the first) or failing to decrement the remainder counter properly, resulting in unevenly sized parts.
Not Handling Empty Parts When k > n
When there are more parts than nodes, some parts must be empty (null). Forgetting to account for this case can lead to index out of bounds errors or incorrect assignments when trying to set heads for parts that have no nodes.
Python code example
from typing import List, Optional
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
length, curr = 0, head
while curr:
curr = curr.next
length += 1
base_len, remainder = length // k, length % k
curr, res = head, []
for i in range(k):
res.append(curr)
for j in range(base_len - 1 + (1 if remainder else 0)):
if not curr:
break
curr = curr.next
remainder -= 1 if remainder else 0
if curr:
curr.next, curr = None, curr.next
return res
C++ code example
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* head, int k) {
int length = 0;
ListNode* curr = head;
while (curr) {
curr = curr->next;
length++;
}
int baseLen = length / k, remainder = length % k;
vector<ListNode*> res(k, nullptr);
curr = head;
for (int i = 0; i < k; i++) {
res[i] = curr;
for (int j = 0; j < baseLen - 1 + (remainder > 0 ? 1 : 0); j++) {
if (!curr) break;
curr = curr->next;
}
if (curr) {
ListNode* temp = curr->next;
curr->next = nullptr;
curr = temp;
}
remainder--;
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.