Split Linked List in Parts

Med

#0679Time: O(N), where N is the number of nodes in the linked list. We traverse the list once to populate the `ArrayList` (O(N)) and then effectively iterate through the `ArrayList` nodes once to form the parts (O(N)).Space: O(N), where N is the number of nodes. This is due to the `ArrayList` used to store all the node references. This is in addition to the O(k) space for the output array.

Data structures

Linked List

Prompt

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.

Example 1:

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:

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.

Constraints:

The number of nodes in the list is in the range [0, 1000].
0 <= Node.val <= 1000
1 <= k <= 50

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a first pass to store all the list nodes into an auxiliary data structure like an ArrayList. After calculating the size of each part based on the total length, we construct the k sublists by picking nodes from the ArrayList and re-linking their next pointers.

Algorithm

1. Create an ArrayList to store ListNode references.
1. Traverse the input linked list from head to tail.
1. In each step of the traversal, add the current node to the ArrayList and count the total number of nodes, N.
1. After the traversal, the size of the ArrayList is the total length N of the list.
1. Calculate the base size of each part: partSize = N / k.
1. Calculate the number of parts that will have an extra node: extraNodes = N % k.
1. Initialize a result array ListNode[] result = new ListNode[k].
1. Initialize an index nodeIndex = 0 to track the current node in the ArrayList.
1. Loop k times, from i = 0 to k-1, to create each part:
- a. Determine the size of the current part: currentPartSize = partSize + (i < extraNodes ? 1 : 0).
- b. If currentPartSize is 0, the part is null. Continue to the next iteration.
- c. Set the head of the current part: result[i] = nodes.get(nodeIndex).
- d. Find the last node of the current part at nodes.get(nodeIndex + currentPartSize - 1).
- e. Set the next pointer of this last node to null to terminate the sublist.
- f. Update the nodeIndex by adding currentPartSize.
1. Return the result array.

Walkthrough

First, we iterate through the entire linked list. During this traversal, we add each ListNode reference to an ArrayList. This process also naturally gives us the total number of nodes, N.

With the total length N, we can determine the size of each of the k parts. The base size for each part is partSize = N / k. The first extraNodes = N % k parts will get one extra node, making their size partSize + 1.

We then create a result array of ListNode of size k. We iterate k times to build each part, using an index to keep track of our position in the ArrayList. For each part, we identify its head node from the ArrayList. Then, we find the last node of that part and set its next pointer to null to terminate the sublist correctly. This method is straightforward but requires extra memory to store all node references.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public ListNode[] splitListToParts(ListNode head, int k) {6        List<ListNode> nodes = new ArrayList<>();7        ListNode current = head;8        while (current != null) {9            nodes.add(current);10            current = current.next;11        }12 13        int N = nodes.size();14        int partSize = N / k;15        int extraNodes = N % k;16 17        ListNode[] result = new ListNode[k];18        int nodeIndex = 0;19        for (int i = 0; i < k; i++) {20            int currentPartSize = partSize + (i < extraNodes ? 1 : 0);21            if (currentPartSize > 0) {22                result[i] = nodes.get(nodeIndex);23                // Get the last node of the current part and set its next to null24                ListNode lastNodeOfPart = nodes.get(nodeIndex + currentPartSize - 1);25                lastNodeOfPart.next = null;26                nodeIndex += currentPartSize;27            } else {28                // This part is empty29                result[i] = null;30            }31        }32        return result;33    }34}

Complexity

Time

O(N), where N is the number of nodes in the linked list. We traverse the list once to populate the `ArrayList` (O(N)) and then effectively iterate through the `ArrayList` nodes once to form the parts (O(N)).

Space

O(N), where N is the number of nodes. This is due to the `ArrayList` used to store all the node references. This is in addition to the O(k) space for the output array.

Trade-offs

Pros

The logic is relatively simple to understand.
Accessing nodes to form sublists is easy with ArrayList's O(1) random access, which simplifies the splitting logic.

Cons

High space complexity of O(N) makes it unsuitable for very long lists or memory-constrained environments.
It is less efficient than an in-place approach due to the overhead of the auxiliary data structure.

This is the optimal approach. It first iterates through the list to find its total length, N. Then, in a second pass, it iterates through the list again, splitting it into k parts in-place without using any extra space proportional to the list's length.

Algorithm

1. Traverse the linked list once to calculate its total length, N.
1. Calculate the base size for each part: partSize = N / k.
1. Calculate the number of parts that will receive an extra node: extraNodes = N % k.
1. Initialize a result array ListNode[] result = new ListNode[k].
1. Initialize a pointer current = head to traverse the list for splitting, and a prev = null pointer to track the tail of each part.
1. Loop k times, from i = 0 to k-1, to create each part:
- a. The head of the current part is current. Store it: result[i] = current.
- b. Determine the size of this part: currentPartSize = partSize + (i < extraNodes ? 1 : 0).
- c. Move the current pointer currentPartSize steps forward to find the start of the next part. Use prev to keep track of the node just before current.
- d. After the inner loop, prev will point to the last node of the current part.
- e. If prev is not null, sever the list by setting prev.next = null.
1. Return the result array.

Walkthrough

The core idea is to first determine the structure of the output (the size of each of the k parts) and then perform the splits in-place.

First Pass: We traverse the linked list from the head to find its total length, N. A simple counter and a pointer are sufficient for this.

Calculate Part Sizes: Just like the previous approach, we calculate the base size partSize = N / k and the number of extra nodes extraNodes = N % k. The first extraNodes parts will have size partSize + 1, and the rest will have size partSize.

Second Pass & Splitting: We initialize our result array of size k. We use a current pointer, initially at the head, to traverse the list. We loop k times to create each part. In each iteration i, we first assign result[i] = current, which marks the beginning of the new part. We then calculate the size for this specific part. To find the end of the current part, we advance a pointer size times. We use a prev pointer to keep track of the last node of the current part. After finding the prev node, we update current to prev.next (which will be the head of the next part) and then set prev.next = null to sever the link, thus creating the split. This process is repeated for all k parts. If the list is exhausted (current becomes null), the remaining parts in the result array will correctly be null.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode[] splitListToParts(ListNode head, int k) {13        // First pass: find the length of the list14        int N = 0;15        ListNode current = head;16        while (current != null) {17            N++;18            current = current.next;19        }20 21        // Calculate part size and extra nodes22        int partSize = N / k;23        int extraNodes = N % k;24 25        ListNode[] result = new ListNode[k];26        current = head;27        ListNode prev = null;28 29        // Second pass: split the list30        for (int i = 0; i < k; i++) {31            result[i] = current;32            33            // Determine the size of the current part34            int currentPartSize = partSize + (i < extraNodes ? 1 : 0);35 36            // Traverse to the end of the current part37            for (int j = 0; j < currentPartSize; j++) {38                prev = current;39                if (current != null) {40                    current = current.next;41                }42            }43            44            // Split the list by setting the last node's next to null45            if (prev != null) {46                prev.next = null;47            }48        }49        return result;50    }51}

Complexity

Time

O(N + k). The first pass takes O(N). The second pass involves a loop of `k` iterations, and inside it, we traverse the nodes. Since each node is visited exactly once by the inner traversal logic across all `k` iterations, the total work for the second pass is O(N). Thus, the total time complexity is O(N + k). Given the constraints, this is effectively O(N).

Space

O(k) for the output array. The auxiliary space used is O(1) for pointers (`current`, `prev`) and variables, which is optimal.

Trade-offs

Pros

Optimal space complexity (O(1) auxiliary space).
Efficient time complexity (O(N)).
Modifies the list in-place, which is memory-efficient.

Cons

Requires two passes over the list. This is a minor issue but could be relevant if the list can only be iterated once (e.g., a data stream).

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode [] splitListToParts ( ListNode root , int k ) { int n = 0 ; ListNode cur = root ; while ( cur != null ) { ++ n ; cur = cur . next ; } // width 表示每一部分至少含有的结点个数 // remainder 表示前 remainder 部分，每一部分多出一个数 int width = n / k , remainder = n % k ; ListNode [] res = new ListNode [ k ]; cur = root ; for ( int i = 0 ; i < k ; ++ i ) { ListNode head = cur ; for ( int j = 0 ; j < width + (( i < remainder ) ? 1 : 0 ) - 1 ; ++ j ) { if ( cur != null ) { cur = cur . next ; } } if ( cur != null ) { ListNode t = cur . next ; cur . next = null ; cur = t ; } res [ i ] = head ; } return res ; } }

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: vector < ListNode *> splitListToParts ( ListNode * head , int k ) { int n = 0 ; for ( ListNode * cur = head ; cur != nullptr ; cur = cur -> next ) { ++ n ; } int cnt = n / k , mod = n % k ; vector < ListNode *> ans ( k , nullptr ); ListNode * cur = head ; for ( int i = 0 ; i < k && cur != nullptr ; ++ i ) { ans [ i ] = cur ; int m = cnt + ( i < mod ? 1 : 0 ); for ( int j = 1 ; j < m ; ++ j ) { cur = cur -> next ; } ListNode * nxt = cur -> next ; cur -> next = nullptr ; cur = nxt ; } return ans ; } };

1# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution : def splitListToParts ( self , root : ListNode , k : int ) -> List [ ListNode ]: n , cur = 0 , root while cur : n += 1 cur = cur . next cur = root width , remainder = divmod ( n , k ) res = [ None for _ in range ( k )] for i in range ( k ): head = cur for j in range ( width + ( i < remainder ) - 1 ): if cur : cur = cur . next if cur : cur . next , cur = None , cur . next res [ i ] = head return res

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem