Problem

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Examples

Example 1:

1
2
3
4
5

Input: head = [1,2,3], k = 5
Output:[[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

1
2
3
4

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output:[[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Solution

Method 1 - First calculate length and then split the list

  1. First, we calculate the total length of the linked list by traversing it with a while loop. We use a helper function size to find the length of the linked list, from Find the length of the linked list.
  2. We calculate two key values:
    • m: The minimum guaranteed size of each part, found by dividing the total length by k.
    • r: The number of extra nodes to distribute among the first r parts, which is the remainder of the division.
  3. We use the curr pointer to traverse the linked list. We then loop through each part:
    • Store the current node as the start of the current part in the parts array.
    • Traverse m + 1 nodes if there are remaining extra nodes (r > 0 for the first r parts); otherwise, traverse m nodes.
    • After traversing the desired number of nodes, disconnect the current part from the rest of the list by setting curr.next to null. Then move curr to the next part’s first node.
  4. Return parts.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        // Calculate the length of the linked list.
        int n = size(head);

        // Calculate the minimum guaranteed part size (n) and the number of
        // extra nodes (r).
        int m = n / k, r = n % k;

        // Create an array of ListNode to store the k parts.
        ListNode[] parts = new ListNode[k];
        ListNode curr = head;

        // Loop through each part.
        for (int i = 0; i < k; i++) {
            parts[i] = curr;
            // Determine the size of the current part.
            int partSize = m + (i < r ? 1 : 0);

            // Traverse partSize nodes.
            for (int j = 1; j < partSize && curr != null; j++) {
                curr = curr.next;
            }

            // If there are more nodes to process, split the list.
            if (curr != null) {
                ListNode nextPart = curr.next;
                curr.next = null;
                curr = nextPart;
            }
        }

        // Return the array of k parts.
        return parts;
    }

    // Helper method to calculate the length of the linked list.
    private int size(ListNode head) {
        int len = 0;
        ListNode curr = head;

        while (curr != null) {
            len++;
            curr = curr.next;
        }

        return len;
    }
}

Complexity

  • ⏰ Time complexity: O(max(n, k)) where n is the length of the linked list
  • 🧺 Space complexity: O(n)