✅Beats 100% -Explained with [ Video ] -C++/Java/Python/ - O(n) Time O(k) Space- Explained in Detail
\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n **I
![Screenshot 2024-09-08 061942.png](https://assets.leetcode.com/users/images/96b13b36-dd7d-45d8-92a4-42163eb6acd8_1725756596.4299555.png)\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n\nhttps://youtu.be/1kWcQuz4VTo\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2900 Subscribers*\n*Current Subscribers: 2804*\n\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about splitting a linked list into k parts such that the sizes of the parts are as equal as possible. Some parts may have a size that differs by at most 1. The goal is to achieve this without creating extra space and by modifying the input linked list itself.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Calculate the Size of the Linked List:\n\n    - Traverse the linked list and count the total number of nodes (size).\n2. Determine the Split Sizes:\n\n    - Each part will have a minimum size of size // k.\n    - There may be some leftover nodes (size % k) which need to be distributed to the first few parts. Therefore, the first size % k parts will have an extra node.\n\n3. Splitting the List into Parts:\n\n    - Initialize a ListNode[] ans of size k to store the resulting parts.\n    - For each part, calculate its size. For the first size % k parts, the size will be splitSize + 1. For the remaining parts, the size will be splitSize.\n    - For each part, traverse the corresponding number of nodes, and then break the list by setting the next pointer of the last node in the current part to null.\n    - Continue this process for all parts and assign the heads of each part to ans[i].\n4. Return the Result:\n\n    - Return the array ans which contains the heads of the k parts.\n\n# Complexity\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Time complexity:\n    - The algorithm traverses the list twice. Once to calculate the total size `(O(n))`, and once to divide it into k parts by reassigning pointers `(O(n))`.\n    - Therefore, the time complexity is `O(n)`, where n is the number of nodes in the linked list.\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- Space complexity: \n    - The space complexity is `O(k)` for the result array `ans` of size `k`.\n    - Since we are modifying the input linked list and not using any additional space for new nodes, the space complexity remains low.\n\n# Step By Step Explanation\n\n### Example Input:\n- **Linked List**: `1 \u2192 2 \u2192 3 \u2192 4 \u2192 5 \u2192 6 \u2192 7 \u2192 8 \u2192 9 \u2192 10`\n- **k**: `3`\n\n### Step 1: Determine the Length of the Linked List\nTraverse the linked list to calculate its total length.\n\n| Node   | Value |\n|--------|-------|\n| Node 1 | 1     |\n| Node 2 | 2     |\n| Node 3 | 3     |\n| Node 4 | 4     |\n| Node 5 | 5     |\n| Node 6 | 6     |\n| Node 7 | 7     |\n| Node 8 | 8     |\n| Node 9 | 9     |\n| Node 10| 10    |\n\n- **Total Length**: `10`\n\n### Step 2: Calculate Size of Each Part\nCompute the basic size and handle any remaining nodes.\n\n- **Basic Size of Each Part**: `Total Length \xF7 k`\n  - `splitSize = 10 \xF7 3 = 3`\n- **Remaining Nodes**: `Total Length % k`\n  - `remainder = 10 % 3 = 1`\n\nThus, the sizes of the parts are:\n- **Part Sizes**: `[4, 3, 3]`\n\n### Step 3: Splitting the List into Parts\nTraverse the list and split it based on the calculated sizes.\n\n#### Part 1 (Size = 4)\n- **Nodes**: `1 \u2192 2 \u2192 3 \u2192 4`\n- **Cut Point**: After node `4`\n\n#### Part 2 (Size = 3)\n- **Nodes**: `5 \u2192 6 \u2192 7`\n- **Cut Point**: After node `7`\n\n#### Part 3 (Size = 3)\n- **Nodes**: `8 \u2192 9 \u2192 10`\n- **Cut Point**: After node `10`\n\n### Summary Table for Each Part:\n\n| Part Number | Nodes in Part     |\n|-------------|--------------------|\n| Part 1      | `1 \u2192 2 \u2192 3 \u2192 4`    |\n| Part 2      | `5 \u2192 6 \u2192 7`        |\n| Part 3      | `8 \u2192 9 \u2192 10`       |\n\n### Key Points to Explain:\n1. **Basic Size Calculation**: The size of each part is determined by dividing the total length of the list by `k`.\n2. **Distribute Extra Nodes**: The first `remainder` number of parts get one extra node.\n3. **Cutting the List**: For each part, traverse the required number of nodes and then cut the list by setting the last node\u2019s `next` pointer to `null`.\n\n---\n\n\n# Code\n```java []\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n\n    public ListNode[] splitListToParts(ListNode head, int k) {\n        ListNode[] ans = new ListNode[k];\n\n        // get total size of linked list\n        int size = 0;\n        ListNode current = head;\n        while (current != null) {\n            size++;\n            current = current.next;\n        }\n\n        // minimum size for the k parts\n        int splitSize = size / k;\n\n        // Remaining nodes after splitting the k parts evenly.\n        // These will be distributed to the first (size % k) nodes\n        int numRemainingParts = size % k;\n\n        current = head;\n        ListNode prev = current;\n        for (int i = 0; i < k; i++) {\n            // create the i-th part\n            ListNode newPart = current;\n            // calculate size of i-th part\n            int currentSize = splitSize;\n            if (numRemainingParts > 0) {\n                numRemainingParts--;\n                currentSize++;\n            }\n\n            // traverse to end of new part\n            int j = 0;\n            while (j < currentSize) {\n                prev = current;\n                current = current.next;\n                j++;\n            }\n            // cut off the rest of linked list\n            if (prev != null) {\n                prev.next = null;\n            }\n\n            ans[i] = newPart;\n        }\n\n        return ans;\n    }\n}\n```\n```C++ []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        vector<ListNode*> ans(k);\n\n        // get total size of linked list\n        int size = 0;\n        ListNode* current = head;\n        while (current != nullptr) {\n            size++;\n            current = current->next;\n        }\n\n        // minimum size for the k parts\n        int splitSize = size / k;\n\n        // Remaining nodes after splitting the k parts evenly.\n        // These will be distributed to the first (size % k) nodes\n        int numRemainingParts = size % k;\n\n        current = head;\n        ListNode* prev = current;\n        for (int i = 0; i < k; i++) {\n            // create the i-th part\n            ListNode* newPart = current;\n            // calculate size of i-th part\n            int currentSize = splitSize;\n            if (numRemainingParts > 0) {\n                numRemainingParts--;\n                currentSize++;\n            }\n\n            // traverse to end of new part\n            int j = 0;\n            while (j < currentSize) {\n                prev = current;\n                if (current != nullptr) {\n                    current = current->next;\n                }\n                j++;\n            }\n\n            // cut off the rest of linked list\n            if (prev != nullptr) {\n                prev->next = nullptr;\n            }\n\n            ans[i] = newPart;\n        }\n\n        return ans;\n    }\n};\n```\n```Python []\n# Definition for singly-linked list.\n# class ListNode(object):\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\n# Definition for singly-linked list.\n\nclass Solution:\n    def splitListToParts(self, head, k):\n        ans = [None] * k\n\n        # Calculate total size of the linked list\n        size = 0\n        current = head\n        while current:\n            size += 1\n            current = current.next\n\n        # Minimum size of each part\n        split_size = size // k\n        remainder = size % k  # Remaining nodes to distribute\n\n        current = head\n        for i in range(k):\n            ans[i] = current\n            current_size = split_size + (1 if remainder > 0 else 0)\n            remainder -= 1\n\n            # Traverse to the end of the current part\n            for _ in range(current_size - 1):\n                if current:\n                    current = current.next\n\n            # Cut the list\n            if current:\n                next_part = current.next\n                current.next = None\n                current = next_part\n\n        return ans\n```\n```JavaScript []\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.next = (next===undefined ? null : next)\n * }\n */\n/**\n * @param {ListNode} head\n * @param {number} k\n * @return {ListNode[]}\n */\nvar splitListToParts = function(head, k) {\n    let ans = new Array(k).fill(null);\n\n    // Calculate total size of the linked list\n    let size = 0;\n    let current = head;\n    while (current) {\n        size++;\n        current = current.next;\n    }\n\n    // Minimum size of each part\n    let splitSize = Math.floor(size / k);\n    let remainder = size % k; // Remaining nodes to distribute\n\n    current = head;\n    let prev = null;\n    for (let i = 0; i < k; i++) {\n        ans[i] = current;\n        let currentSize = splitSize + (remainder > 0 ? 1 : 0);\n        remainder--;\n\n        // Traverse to the end of the current part\n        for (let j = 0; j < currentSize; j++) {\n            prev = current;\n            current = current.next;\n        }\n\n        // Cut the list\n        if (prev) prev.next = null;\n    }\n\n    return ans;\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/a1302400-8d56-464c-812a-a405876de71d_1725756380.3916013.png)\n
['Linked List', 'Python', 'C++', 'Java', 'JavaScript']