> For the complete documentation index, see [llms.txt](https://code-render.gitbook.io/leetcode-editorials/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-render.gitbook.io/leetcode-editorials/09-september/06-split-linked-list-in-parts.md).

# 06. Split Linked List in Parts

The problem can be found at the following link: [Question Link](https://leetcode.com/problems/split-linked-list-in-parts/)

## My Approach

The key insight here is that we can efficiently split the linked list into equal-sized parts by calculating the minimum guaranteed size of each part (n) and distributing any extra nodes (r) as evenly as possible among the first r parts. This approach ensures that we meet both conditions specified in the problem statement.

By maintaining two pointers (node and prev) and updating them as we traverse the linked list, we can keep track of the current part and efficiently split the list into k parts.

1. Create a vector of ListNode pointers called "parts" with k elements, all initialized to nullptr. This vector will store the head nodes of the k sublists.
2. Initialize a variable "len" to 0. This variable will be used to calculate the total number of nodes in the linked list.
3. Loop through the linked list using a pointer "node" starting from the "root" node.
   * For each node in the list, increment the "len" variable by 1, counting the total number of nodes.
4. Calculate two values, "n" and "r":
   * "n" represents the approximate number of nodes in each of the k sublists, which is obtained by dividing "len" by "k."
   * "r" represents the remainder of the division "len % k," which accounts for the number of sublists that need to have an extra node to balance them.
5. Initialize two pointers, "node" (pointing to the head of the original list) and "prev" (initialized to nullptr).
6. Loop through the process of splitting the linked list into k parts:
   * Iterate from 0 to k-1 in a loop (i.e., for each of the k sublists).
   * Assign the current "node" to the "i"-th element of the "parts" vector. This marks the beginning of the sublist.
   * Loop "j" from 0 to "n + (r > 0)" times. This inner loop traverses through the sublist, where "n" is the average number of nodes per sublist, and "r > 0" indicates that some sublists need an extra node.
   * Inside the inner loop, update the "prev" pointer to point to the current "node," and move the "node" pointer to the next node in the original list.
   * Set the "next" pointer of "prev" to nullptr. This effectively cuts off the current sublist from the original list.
7. After the loop completes, the "parts" vector contains the k sublists, and each sublist is separated from the original list.
8. Return the "parts" vector, which now holds the head nodes of the k sublists.

## Time and Auxiliary Space Complexity

* **Time Complexity**: `O(n)`
* **Auxiliary Space Complexity**: `O(1)`

## Code (C++)

```cpp

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        vector<ListNode*> parts(k, nullptr);

        int len = 0;
        for (ListNode* node = root; node; node = node->next){
            len++;
        }

        int n = len / k, r = len % k;
        ListNode* node = root, *prev = nullptr;

        for (int i = 0; node && i < k; i++, r--) {
            
            parts[i] = node;
            for (int j = 0; j < n + (r > 0); j++) {
                prev = node;
                node = node->next;
            }
            
            prev->next = nullptr;
        }
        return parts;
    }
};

```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://leetcode.com/discuss/general-discussion). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a `⭐ star` to the [rishabhv12/Daily-Leetcode-Solution](https://github.com/rishabhv12/Daily-Leetcode-Solution) repository.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://code-render.gitbook.io/leetcode-editorials/09-september/06-split-linked-list-in-parts.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.