# Split Linked List in Parts
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/split-linked-list-in-parts)
Canonical: https://scaleengineer.com/dsa/problems/split-linked-list-in-parts
**Data structures:** Linked List
---
## 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_.

**Example 1:**

![](https://assets.glich.co/dsa/split-linked-list-in-parts/image0.jpg) 

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

![](https://assets.glich.co/dsa/split-linked-list-in-parts/image1.jpg) 

**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
## Using an Auxiliary List
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.
**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.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        List<ListNode> nodes = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            nodes.add(current);
            current = current.next;
        }

        int N = nodes.size();
        int partSize = N / k;
        int extraNodes = N % k;

        ListNode[] result = new ListNode[k];
        int nodeIndex = 0;
        for (int i = 0; i < k; i++) {
            int currentPartSize = partSize + (i < extraNodes ? 1 : 0);
            if (currentPartSize > 0) {
                result[i] = nodes.get(nodeIndex);
                // Get the last node of the current part and set its next to null
                ListNode lastNodeOfPart = nodes.get(nodeIndex + currentPartSize - 1);
                lastNodeOfPart.next = null;
                nodeIndex += currentPartSize;
            } else {
                // This part is empty
                result[i] = null;
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Create an `ArrayList` to store `ListNode` references.
- 2. Traverse the input linked list from `head` to tail.
- 3. In each step of the traversal, add the current node to the `ArrayList` and count the total number of nodes, `N`.
- 4. After the traversal, the size of the `ArrayList` is the total length `N` of the list.
- 5. Calculate the base size of each part: `partSize = N / k`.
- 6. Calculate the number of parts that will have an extra node: `extraNodes = N % k`.
- 7. Initialize a result array `ListNode[] result = new ListNode[k]`.
- 8. Initialize an index `nodeIndex = 0` to track the current node in the `ArrayList`.
- 9. 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`.
- 10. Return the `result` array.

## Two-Pass, In-place Splitting
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.
**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.
**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).
### Explanation
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`.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        // First pass: find the length of the list
        int N = 0;
        ListNode current = head;
        while (current != null) {
            N++;
            current = current.next;
        }

        // Calculate part size and extra nodes
        int partSize = N / k;
        int extraNodes = N % k;

        ListNode[] result = new ListNode[k];
        current = head;
        ListNode prev = null;

        // Second pass: split the list
        for (int i = 0; i < k; i++) {
            result[i] = current;
            
            // Determine the size of the current part
            int currentPartSize = partSize + (i < extraNodes ? 1 : 0);

            // Traverse to the end of the current part
            for (int j = 0; j < currentPartSize; j++) {
                prev = current;
                if (current != null) {
                    current = current.next;
                }
            }
            
            // Split the list by setting the last node's next to null
            if (prev != null) {
                prev.next = null;
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Traverse the linked list once to calculate its total length, `N`.
- 2. Calculate the base size for each part: `partSize = N / k`.
- 3. Calculate the number of parts that will receive an extra node: `extraNodes = N % k`.
- 4. Initialize a result array `ListNode[] result = new ListNode[k]`.
- 5. Initialize a pointer `current = head` to traverse the list for splitting, and a `prev = null` pointer to track the tail of each part.
- 6. 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`.
- 7. Return the `result` array.

# Solutions
### Java

```java
/** * 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 ; } }
```

### CPP

```cpp
/** * 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 ; } };
```

### Python

```python
# 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
```