Sponsored
Sponsored
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode** splitListToParts(struct ListNode* root, int k, int* returnSize) {
10 struct ListNode** parts = malloc(sizeof(struct ListNode*) * k);
11 for (int i = 0; i < k; i++)
12 parts[i] = NULL;
13
14 int length = 0;
15 struct ListNode* node = root;
16 while (node) {
17 length++;
18 node = node->next;
19 }
20
21 int partSize = length / k;
22 int extraNodes = length % k;
23
24 node = root;
25 for (int i = 0; i < k && node; i++) {
26 parts[i] = node;
27 int currentPartSize = partSize + (i < extraNodes ? 1 : 0);
28 for (int j = 1; j < currentPartSize; j++) {
29 node = node->next;
30 }
31 struct ListNode* nextPart = node->next;
32 node->next = NULL;
33 node = nextPart;
34 }
35 *returnSize = k;
36 return parts;
37}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.
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;
}
}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.