
Description
The problem involves splitting a singly-linked list into k
parts. Each part should be as equal in size as possible, and any excess nodes should be added to the first few parts. The goal is to return an array where each element represents the head of one of these parts.
Intuition
To solve this problem, we need to determine how many nodes each part should have. First, by counting the total number of nodes in the list, we can decide the base size of each part and distribute any remaining nodes to the first few parts. This ensures that the parts are as balanced as possible in terms of size.
Approach
- Counting the Nodes: We start by counting the total number of nodes in the linked list.
- Calculate Part Sizes: If the number of nodes
count
is less than or equal tok
, each node will form its own part, with the remaining parts beingnull
. Ifcount
is greater thank
, each part will get at leastcount // k
nodes. The firstcount % k
parts will receive one extra node. - Splitting the List: Traverse the list again, and for each part, we traverse the number of nodes assigned to that part. After completing the traversal for a part, we sever the list and move to the next part.
Complexity
Time Complexity:
O(n), where n
is the number of nodes in the linked list. We traverse the list twice—once to count the nodes and once to split the list.
Space Complexity:
O(k), where k
is the number of parts. We need additional space to store the resulting parts array.
Code
C++
class Solution {
public:
vector splitListToParts(ListNode* head, int k) {
vector arr(k, nullptr);
if (k == 1) {
arr[0] = head;
return arr;
}
// Count the total number of nodes
int count = 0;
ListNode* current = head;
while (current != nullptr) {
count++;
current = current->next;
}
if (count <= k) {
current = head;
for (int i = 0; i < count; i++) {
arr[i] = head;
ListNode* tail = head;
head = head->next;
tail->next = nullptr;
}
return arr;
}
int extraCount = count % k;
int elementsCount = count / k;
for (int i = 0; i < k; i++) {
arr[i] = head;
int currentPartSize = elementsCount + (extraCount > 0 ? 1 : 0);
extraCount--;
for (int j = 0; j < currentPartSize - 1; j++) {
head = head->next;
}
if (head != nullptr) {
ListNode* tail = head;
head = head->next;
tail->next = nullptr;
}
}
return arr;
}
};
Python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def splitListToParts(self, head: ListNode, k: int):
# If k is 1, return the head
if k == 1:
return [head]
# Count the total number of nodes
count = 0
current = head
while current:
count += 1
current = current.next
arr = [None] * k
if count <= k:
for i in range(count):
arr[i] = head
tail = head
head = head.next
tail.next = None
return arr
extraCount = count % k
elementsCount = count // k
for i in range(k):
arr[i] = head
currentPartSize = elementsCount + (1 if extraCount > 0 else 0)
extraCount -= 1
for j in range(currentPartSize - 1):
head = head.next
if head:
tail = head
head = head.next
tail.next = None
return arr
Java
public class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
if (k == 1) {
return new ListNode[] { head };
}
int count = 0;
ListNode current = head, tail;
ListNode[] arr = new ListNode[k];
// Count the total number of nodes
while (current != null) {
count++;
current = current.next;
}
if (count <= k) {
for (int i = 0; i < count; i++) {
arr[i] = head;
tail = head;
head = head.next;
tail.next = null;
}
for (int i = count; i < k; i++) {
arr[i] = null;
}
return arr;
}
int extraCount = count % k, elementsCount = count / k;
for (int i = 0; i < k; i++) {
arr[i] = head;
int currentPartSize = elementsCount + (extraCount > 0 ? 1 : 0);
extraCount--;
for (int j = 0; j < currentPartSize - 1; j++) {
head = head.next;
}
tail = head;
head = head.next;
tail.next = null;
}
return arr;
}
}
JavaScript
var splitListToParts = function(head, k) {
if(k==1) {
return [head]
}
let count = 0, current = head, tail, arr = []
while(current) {
count++
current = current.next
}
if(count <= k) {
for(let i=0; i0) {
tail = head
head = head.next
extraCount--
}
tail.next = null
}
return arr
};