Dare2Solve
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.
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.
count
is less than or equal to k
, each node will form its own part, with the remaining parts being null
. If count
is greater than k
, each part will get at least count // k
nodes. The first count % k
parts will receive one extra node.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.
O(k), where k
is the number of parts. We need additional space to store the resulting parts array.
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* head, int k) {
vector<ListNode*> 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;
}
};
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
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;
}
}
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; i<count; i++) {
arr.push(head)
tail = head
head = head.next
tail.next = null
}
for(let i=0; i<k-count; i++) {
arr.push(null)
}
return arr
}
let extraCount = count % k, elementsCount = count / k
for(let i=0; i<k; i++) {
arr.push(head)
if(elementsCount%2 == 0) {
elementsCount++
}
for(let j=0; j<elementsCount-1; j++) {
tail = head
head = head.next
}
if(extraCount>0) {
tail = head
head = head.next
extraCount--
}
tail.next = null
}
return arr
};