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:

  1. 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.

  2. 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.

  3. Initialize an array of k elements to hold the resulting linked list parts, setting each element initially as None.

  4. 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 index i is less than the remainder 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 to None.
    • 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.

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:

  1. 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.

  2. Division Logic: The key computation happens with the divmod function, which returns two values: width and remainder.

    • 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 by k.
  3. Resulting Array Creation: An array res is created and pre-filled with None to hold the final parts. This prepares the groundwork for the later storage of the head nodes of each part.

  4. 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 node cur, which becomes the head of the new part.
    • A nested loop then runs exactly width times, and if the current part index i is less than the remainder, 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 to None. 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.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example 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:

1Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
2k = 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:

1n = 7 (number of nodes in the list)

Step 2: Division Logic

Using the divmod function:

1width, remainder = divmod(7, 3)
2
3width = 2 (base size of each part)
4remainder = 1 (one part will have one extra node)

Step 3: Resulting Array Creation

Create the array to hold the results with None initially:

1res = [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 because i < 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].
  • 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 because i >= 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    1 -> 2 -> 3,
3    4 -> 5 -> 6,
4    7
5]

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄