725. Split Linked List in Parts
Problem Description
The problem presents a scenario where we are given the head of a singly linked list and an integer k
. Our task is to divide this linked list into k
consecutive parts. The objective here is to distribute the nodes of the linked list as evenly as possible among the k
parts, which means each part's length should not differ by more than one compared to the other parts.
Since the size division might not always be perfect (for example, when the number of nodes is not a multiple of k
), some parts could end up being empty (null).
It's important to note that the parts need to be split by their original order in the list. And when there's a discrepancy in size due to the division process (which means some parts are allowed to have one more node than the others), the larger parts should appear earlier in the resulting array of linked list parts.
The final goal is to return an array of the k
parts created from the original list.
Intuition
To arrive at a solution, we can follow the outlined steps:
-
Count the number of nodes in the given linked list. This step will help us to know how to divide the linked list nodes into
k
parts as equally as possible. -
Compute the width (the number of nodes that each part would have if nodes were evenly distributed) and remainder (the number of parts that will have one extra node) using the division and modulo operators, respectively.
-
Initialize an array of
k
elements to hold the resulting linked list parts, setting each element initially asNone
. -
Iterate
k
times, once for each part we need to create:- In each iteration, we consider the current node (
cur
) as the new part's head. - Then, we skip
width
nodes, plus one more if the indexi
is less than theremainder
since those parts are allowed to have one additional node. - After skipping the required number of nodes, we disconnect the current part from the rest of the linked list by setting the
next
pointer of the current node toNone
. - Move the
cur
pointer to the next node in the original list, which will then serve as the head for the next part (if any). - Store the head of the current part in our result array.
- In each iteration, we consider the current node (
By going through this process, we end up dividing the list into k
parts satisfying the size requirements stated in the problem, and we return the array containing these parts as our final result.
Learn more about Linked List patterns.
Solution Approach
The implementation of the solution involves a step-by-step traversal and division of the linked list, which uses basic concepts of linked list manipulation. The approach doesn't use any advanced algorithms or patterns but is rather a straightforward application of linked list operations. Here are the details:
-
Initialization: The number of nodes in the linked list is counted by traversing the list once with a simple while loop. This is stored in the variable
n
. -
Division Logic: The key computation happens with the
divmod
function, which returns two values:width
andremainder
.width
is the base size of each part when nodes are evenly distributed.remainder
is the count of initial parts that should have one extra node because the nodes cannot be perfectly divided byk
.
-
Resulting Array Creation: An array
res
is created and pre-filled withNone
to hold the final parts. This prepares the groundwork for the later storage of the head nodes of each part. -
List Division: Now comes the division of the list into
k
parts iteratively:- For each of the
k
parts, the loop starts with the current nodecur
, which becomes the head of the new part. - A nested loop then runs exactly
width
times, and if the current part indexi
is less than theremainder
, it runs an additional time. This loop effectively skips a number of nodes corresponding to the size of the current part. - Once the end of the current part is reached, the next node is disconnected from the current part by setting the
next
property of the last node in the current part toNone
. This is crucial as it ensures the current part is not linked to the next part. - The head node of the current part is then stored in the
res
array. - The
cur
pointer is updated to reference the next node in the original list, which will be the head of the following part.
- For each of the
By the end of these steps, we have an array res
with k
elements, each referencing the head of a sublist that conforms to the problem's division requirements. The simplicity of this approach lies in its effective use of basic linked list operations such as traversal, node counting, and reassignment of the next
pointer to split the list as needed.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach to a small example to illustrate how it works in practice.
Assume we have the following singly linked list and integer k
:
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 k = 3
In this example, we want to split the linked list into 3 parts as evenly as possible.
Step 1: Initialization
Count the number of nodes in the linked list:
n = 7 (number of nodes in the list)
Step 2: Division Logic
Using the divmod
function:
width, remainder = divmod(7, 3) width = 2 (base size of each part) remainder = 1 (one part will have one extra node)
Step 3: Resulting Array Creation
Create the array to hold the results with None
initially:
res = [None, None, None]
Step 4: List Division
Now divide the linked list into k
parts:
-
First iteration (i = 0 < remainder):
- Current node
cur
is at 1. - Skip
width + 1
nodes becausei < remainder
. - New part: 1 -> 2 -> 3 (since
width
is 2 but we add 1 for the remainder). - Disconnect third node's
next
pointer. - Move
cur
to node 4. - Resulting array receives the first part:
[1 -> 2 -> 3, None, None]
.
- Current node
-
Second iteration (i = 1 < remainder):
cur
is now at node 4.- Skip
width + 1
nodes again. - New part: 4 -> 5 -> 6.
- Disconnect sixth node's
next
pointer. - Move
cur
to node 7. - Resulting array now looks like:
[1 -> 2 -> 3, 4 -> 5 -> 6, None]
.
-
Third iteration (i = 2 >= remainder):
cur
is now at node 7.- Skip
width
nodes only becausei >= remainder
. - New part is just node 7.
- No need to disconnect since it's the end of the list.
- All other elements in the array are unchanged.
- Final array is:
[1 -> 2 -> 3, 4 -> 5 -> 6, 7]
.
The final output is an array of 3 linked lists as evenly distributed as possible, satisfying the problem's constraints.
The resulting linked list parts contained in our res
array will look like:
[ 1 -> 2 -> 3, 4 -> 5 -> 6, 7 ]
Each step consistently applies the logic of linked list division, accounting for both the base width and the remainder to ensure a fair distribution of nodes across the resulting sublists.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, val=0, next=None):
4 self.val = val
5 self.next = next
6
7
8class Solution:
9 def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
10 # Initialize the length of the list and a temporary node to iterate through the list
11 list_length, current_node = 0, root
12 # Calculate the total length of the list
13 while current_node:
14 list_length += 1
15 current_node = current_node.next
16
17 # Reset the current_node back to the beginning of the list
18 current_node = root
19 # Determine the size of each part and the extra nodes to distribute
20 part_size, extra_nodes = divmod(list_length, k)
21 # Initialize the result list with None placeholders for each part
22 result = [None for _ in range(k)]
23
24 # Split the list into k parts
25 for i in range(k):
26 # The beginning of the current part
27 part_head = current_node
28 # Calculate the number of nodes this part should have
29 current_part_size = part_size + (i < extra_nodes)
30
31 # Iterate through the current part's nodes, stopping before the last node
32 for j in range(current_part_size - 1):
33 if current_node:
34 current_node = current_node.next
35
36 # If there are nodes in the current part, disconnect this part from the next one
37 if current_node:
38 # Temporarily store the next part
39 next_part = current_node.next
40 # Disconnect the current part from the rest of the list
41 current_node.next = None
42 # Move the current_node to the beginning of the next part
43 current_node = next_part
44
45 # Update the result with the head of the current part
46 result[i] = part_head
47
48 return result
49
1/**
2 * Definition for singly-linked list.
3 */
4public class ListNode {
5 int val;
6 ListNode next;
7 ListNode(int x) { val = x; }
8}
9
10class Solution {
11 /**
12 * Splits the linked list into k consecutive parts.
13 *
14 * @param root The head of the linked list.
15 * @param k The number of parts to split the list into.
16 * @return An array of ListNode where each element is the head of a part of the split list.
17 */
18 public ListNode[] splitListToParts(ListNode root, int k) {
19 int length = 0;
20 ListNode current = root;
21
22 // Calculate the total length of the linked list.
23 while (current != null) {
24 ++length;
25 current = current.next;
26 }
27
28 // Calculate the minimum number of nodes each part should have.
29 int minPartSize = length / k;
30 // Calculate how many parts should have an extra node.
31 int extraNodes = length % k;
32
33 ListNode[] result = new ListNode[k];
34 current = root;
35
36 // Divide the list into parts.
37 for (int i = 0; i < k; ++i) {
38 ListNode partHead = current;
39 // Determine the size of the current part,
40 // which is minPartSize plus one if this part is supposed to have an extra node.
41 int currentPartSize = minPartSize + (i < extraNodes ? 1 : 0);
42
43 // Traverse to the end of the current part.
44 for (int j = 0; j < currentPartSize - 1; ++j) {
45 if (current != null) {
46 current = current.next;
47 }
48 }
49
50 // Detach the current part from the remainder of the list.
51 if (current != null) {
52 ListNode nextPartHead = current.next;
53 current.next = null;
54 current = nextPartHead;
55 }
56
57 // Add the head of the current part to the result array.
58 result[i] = partHead;
59 }
60
61 return result;
62 }
63}
64
1/**
2 * Definition for singly-linked list.
3 */
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(nullptr) {}
8};
9
10class Solution {
11public:
12 /**
13 * Splits the linked list into k consecutive parts.
14 *
15 * @param root The head of the linked list.
16 * @param k The number of parts to split the list into.
17 * @return A vector of ListNode pointers where each element is the head of a part of the split list.
18 */
19 vector<ListNode*> splitListToParts(ListNode* root, int k) {
20 // Initialize the vector that will hold the parts' heads.
21 vector<ListNode*> result(k, nullptr);
22
23 // Calculate the total length of the linked list.
24 int length = 0;
25 ListNode* current = root;
26 while (current != nullptr) {
27 ++length;
28 current = current->next;
29 }
30
31 // Calculate the minimum number of nodes each part should have.
32 int minPartSize = length / k;
33 // Calculate how many parts should have an extra node.
34 int extraNodes = length % k;
35
36 current = root;
37
38 // Divide the list into parts.
39 for (int i = 0; i < k; ++i) {
40 ListNode* partHead = current;
41 // Determine the size of the current part,
42 // which is minPartSize plus one if this part is supposed to have an extra node.
43 int currentPartSize = minPartSize + (i < extraNodes ? 1 : 0);
44
45 // Traverse to the end of the current part.
46 for (int j = 0; j < currentPartSize - 1; ++j) {
47 if (current != nullptr) {
48 current = current->next;
49 }
50 }
51
52 // Detach the current part from the remainder of the list.
53 if (current != nullptr) {
54 ListNode* nextPartHead = current->next;
55 current->next = nullptr;
56 current = nextPartHead;
57 }
58
59 // Add the head of the current part to the result vector.
60 result[i] = partHead;
61 }
62
63 return result;
64 }
65};
66
1// Type definition for singly-linked list.
2type ListNode = {
3 val: number;
4 next: ListNode | null;
5}
6
7function splitListToParts(root: ListNode | null, k: number): (ListNode | null)[] {
8 // Initialize the length of the linked list.
9 let length = 0;
10 let current: ListNode | null = root;
11
12 // Calculate the total length of the linked list.
13 while (current !== null) {
14 length++;
15 current = current.next;
16 }
17
18 // Calculate the minimum number of nodes each part should have.
19 const minPartSize = Math.floor(length / k);
20 // Calculate how many parts should have an extra node.
21 const extraNodes = length % k;
22
23 // Resulting array of heads for each part of the split list.
24 const result: (ListNode | null)[] = new Array(k).fill(null);
25 current = root;
26
27 // Divide the linked list into k parts.
28 for (let i = 0; i < k; i++) {
29 let partHead = current;
30 // Determine the size of the current part,
31 // which is minPartSize plus one if this part is supposed to have an extra node.
32 let currentPartSize = minPartSize + (i < extraNodes ? 1 : 0);
33
34 // Traverse to the end of the current part.
35 for (let j = 1; j < currentPartSize && current !== null; j++) {
36 current = current.next;
37 }
38
39 // If the end of the current part is found, detach this part from the rest of the list.
40 if (current !== null) {
41 let nextPartHead = current.next;
42 current.next = null; // Detach the current part.
43 current = nextPartHead; // Move to the next part of the list.
44 }
45
46 // Assign the head of the current part to the result.
47 result[i] = partHead;
48 }
49
50 // Return the array containing the heads of each part of the split list.
51 return result;
52}
53
Time and Space Complexity
The time complexity of the given code is O(n + k)
, where n
is the number of elements in the singly-linked list, and k
is the number of parts to split the list into.
The first while
loop runs through the entire list to count the number of nodes, which takes O(n)
time.
After that, the for
loop runs k
times to create the k
parts. Each part might require up to width + 1
iterations to set the next pointer to None
and advance the cur
pointer. Since width = n // k
, in the worst case, this inner loop can be considered a constant operation because it doesn't scale with n
(since the number of iterations within each of the k
outer iterations rounds to n
total). Thus, the entire for
loop still takes O(k)
time.
So, total time complexity is the sum of the two primary operations which gives us O(n) + O(k)
.
The space complexity of the code is O(k)
because an array of k
elements is created to store the heads of the parts of the linked list. There are no other data structures that scale with the size of the input, and the list slices are created in-place without any extra space, except the output array.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!