Efficient Split Linked List Solution | C++ Java Py3 | O(n) | 3ms Beats 89.05%
\uD83C\uDF1F \n\n---\n\n## Intuition\nThe problem requires splitting a linked list into k parts with as equal size as possible. To approach this, we first calcu
\uD83C\uDF1F \n\n---\n\n## Intuition\nThe problem requires splitting a linked list into $$k$$ parts with as equal size as possible. To approach this, we first calculate the total length of the linked list, then compute the base size of each part. The first few parts may need to be slightly larger if the list length isn\'t divisible by $$k$$. After that, we traverse the list, disconnecting it as we go, and return an array of the split parts.\n\n## Approach\nWe start by calculating the total number of nodes in the linked list. The base size of each part will be $$n / k$$, and the remaining nodes ($$n % k$$) are distributed across the first few parts to make sure the sizes differ by at most one. Then we traverse the list, creating sublists for each part and adjusting the $$next$$ pointers to separate them.\n\n## Complexity\n- **Time Complexity** $$O(n)$$, where $$n$$ is the number of nodes in the linked list. We traverse the list to count the nodes and split the list in a second pass.\n- **Space Complexity** $$O(k)$$ for the resulting array of $$k$$ parts.\n\n## Code\n\n```cpp []\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        int n{0};\n        for (auto* p = head; p; p = p->next) n++; \n        int size = n / k, extra = n % k; \n        vector<ListNode*> res(k);\n        for (auto* p = head; p; extra--, k--) {\n            res[res.size() - k] = p; \n            for (int i = 1; i < size + (extra > 0); i++) p = p->next;\n            auto* tmp = p->next;\n            p->next = nullptr; \n            p = tmp;\n        }\n        return res;\n    }\n};\n```\n\n```java []\nclass Solution {\n    public ListNode[] splitListToParts(ListNode head, int k) {\n        int n = 0;\n        for (ListNode p = head; p != null; p = p.next) n++; \n        int size = n / k, extra = n % k;\n        ListNode[] res = new ListNode[k];\n        for (ListNode p = head; p != null; extra--, k--) {\n            res[res.length - k] = p; \n            for (int i = 1; i < size + (extra > 0 ? 1 : 0); i++) p = p.next; \n            ListNode tmp = p.next;\n            p.next = null; \n            p = tmp; \n        }\n        return res;\n    }\n}\n```\n\n```python []\nclass Solution:\n    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n        n, p = 0, head\n        while p:\n            n += 1\n            p = p.next \n        size, extra = divmod(n, k)\n        res = []\n        p = head\n        for _ in range(k):\n            res.append(p)\n            for _ in range(size + (extra > 0) - 1 if p else 0):\n                p = p.next\n            if p:\n                tmp = p.next\n                p.next = None \n                p = tmp\n            extra -= 1\n        return res\n```\n\n---\n- ![image.png](https://assets.leetcode.com/users/images/425fb619-e77b-48fc-be55-aa264544611d_1725765737.3242157.png)\n---
['C++', 'Java', 'Python3']