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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val = 0, ListNode next = null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode[] SplitListToParts(ListNode root, int k) {
12 ListNode[] parts = new ListNode[k];
13 int length = 0;
14 ListNode node = root;
15 while (node != null) {
16 length++;
17 node = node.next;
18 }
19 int partSize = length / k;
20 int extraNodes = length % k;
21 node = root;
22 for (int i = 0; i < k && node != null; i++) {
23 parts[i] = node;
24 int currentSize = partSize + (i < extraNodes ? 1 : 0);
25 for (int j = 1; j < currentSize; j++) {
26 node = node.next;
27 }
28 ListNode nextPart = node.next;
29 node.next = null;
30 node = nextPart;
31 }
32 return parts;
33 }
34}The C# solution follows the approach of calculating the length, determining part sizes, and iteratively splitting the list. It uses an array to store the result and manages linked list pointers to break the list into smaller parts.
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
This Python solution combines looping and splitting in one traversal of the linked list. The use of divmod simplifies the calculation of base size and extra nodes needed, achieving a concise solution for the node management.