⚡️Fast & Optimal💡 | 💯 C++ & Python Solution 🚀 | O(n) Time⏳ | Beginner Friendly 🎯
Intuition\nThe problem asks to split a singly linked list into k parts, where the lengths of the parts differ by at most one. If the number of nodes in the link
# Intuition\nThe problem asks to split a singly linked list into `k` parts, where the lengths of the parts differ by at most one. If the number of nodes in the linked list isn\'t perfectly divisible by `k`, some parts will be longer, and we need to assign the extra nodes to the earlier parts.\n\n# Approach\n\nWe will solve the problem in a systematic manner with the following steps:\n\n### 1. Calculate the Total Number of Nodes:\n\nFirst, we traverse the entire linked list once to count the total number of nodes (`n`).\n\n### 2. Determine the Size of Each Part:\n\nUsing the total number of nodes (`n`), we calculate:\n\n- **Base part size**: This is the minimum size of each part, calculated as `n // k` (integer division).\n- **Extra nodes**: This is the number of parts that will have one extra node, calculated as `n % k` (remainder).\n\n3. Split the List into Parts:\n\n- We iterate through the list again, and for each part:\n    - Assign `partSize + 1` nodes to the first `extra` parts.\n    - Assign exactly `partSize` nodes to the remaining parts.\n- During this process, we break the connections between parts by setting the `next` pointer of the last node in each part to `nullptr`.\n\n## Dry Run Example:\n\n#### Input:\n\nLinked list: `[1,2,3,4,5,6,7,8,9,10]`, `k=3`\n\n1. Count total nodes (`n`):\n\nTraverse the list: `n = 10` (There are 10 nodes in the list).\n\n2. Calculate part sizes:\n\n- Base part size: `n // k = 10 // 3 = 3` (Each part will have at least 3 nodes).\n- Extra nodes: `n % k = 10 % 3 = 1` (There is 1 extra node to be distributed to the first part).\n\n3. Split the list:\n\n- First part: Take 4 nodes (3 base size + 1 extra): `[1,2,3,4]`\n- Second part: Take 3 nodes: `[5,6,7]`\n- Third part: Take 3 nodes: `[8,9,10]`\n\nThus, the result will be `[[1,2,3,4], [5,6,7], [8,9,10]]`.\n\n\n# Complexity\n- **Time complexity**: The algorithm performs one pass to count the nodes (`O(n)`) and another pass to split the list into parts (`O(n)`). Thus, the overall time complexity is \uD835\uDC42(\uD835\uDC5B).\n\n- **Space complexity**: The algorithm uses an additional array of size `k` to store the `k` parts, so the space complexity is \uD835\uDC42(\uD835\uDC58).\n\n# Code\n```cpp []\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        // Step 1: Count the total number of nodes in the list\n        int n = 0;\n        for (ListNode* temp = head; temp; temp = temp->next) {\n            n++;\n        }\n\n        // Step 2: Calculate the base size of each part and the number of extra nodes\n        int partSize = n / k;  // Base size of each part\n        int extra = n % k;     // Extra nodes to be distributed among the first few parts\n\n        // Step 3: Prepare the result vector and initialize to nullptr\n        vector<ListNode*> result(k, nullptr);\n        ListNode *curr = head, *prev = nullptr;\n\n        // Step 4: Iterate through each part to split the list\n        for (int i = 0; i < k && curr != nullptr; ++i) {\n            result[i] = curr;\n            int currPartSize = partSize + (i < extra ? 1 : 0); // Add one extra node if `i` is less than `extra`\n\n            // Traverse through the current part\n            for (int j = 0; j < currPartSize; ++j) {\n                prev = curr; \n                curr = curr->next; \n            }\n\n            // Disconnect the current part from the rest of the list\n            if (prev != nullptr) {\n                prev->next = nullptr;\n            }\n        }\n\n        return result;\n    }\n};\n\n```\n\n```python []\n# Definition for singly-linked list.\nclass ListNode(object):\n    def __init__(self, val=0, next=None):\n        self.val = val\n        self.next = next\n\nclass Solution(object):\n    def splitListToParts(self, head, k):\n        """\n        :type head: ListNode\n        :type k: int\n        :rtype: List[ListNode]\n        """\n        # Step 1: Count the total number of nodes\n        n = 0\n        temp = head\n        while temp:\n            n += 1\n            temp = temp.next\n        \n        # Step 2: Determine the base part size and extra nodes\n        part_size = n // k  # Base size of each part\n        extra = n % k       # Extra nodes to distribute\n\n        # Step 3: Create the result list and split the linked list\n        result = []\n        curr = head\n        \n        for i in range(k):\n            result.append(curr)\n            curr_part_size = part_size + (1 if i < extra else 0)\n\n            # Move to the end of the current part\n            prev = None\n            for j in range(curr_part_size):\n                prev = curr\n                if curr:\n                    curr = curr.next\n\n            # Disconnect current part from the rest of the list\n            if prev:\n                prev.next = None\n\n        return result\n\n```
['Linked List', 'C++', 'Python3']