Python | Greedy Partitioning
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Option
[see the Successfully Accepted Submission](https://leetcode.com/problems/split-linked-list-in-parts/submissions/1217157702/?envType=daily-question&envId=2024-09-08)\n\n# Code\n```python3 []\nclass Solution:\n    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n        # Step 1: Count the number of nodes\n        current = head\n        count = 0\n        while current:\n            count += 1\n            current = current.next\n        \n        # Step 2: Calculate the size of each part and the number of extra nodes\n        part_size, extra_nodes = divmod(count, k)\n        \n        # Step 3: Split the list into k parts\n        current = head\n        result = []\n        for i in range(k):\n            part_head = current\n            for j in range(part_size - 1 + (i < extra_nodes)):\n                if current:\n                    current = current.next\n            if current:\n                next_node = current.next\n                current.next = None\n                current = next_node\n            result.append(part_head)\n        \n        return result\n        \n```\n\n### Algorithm Steps:\n\n1. **Step 1: Count the number of nodes in the linked list**\n    - Initialize a `current` pointer to `head` and a `count` variable to 0.\n    - Traverse the list by moving the `current` pointer one node at a time, while incrementing `count`.\n    - After traversing the list, `count` will hold the total number of nodes in the linked list.\n\n2. **Step 2: Determine the size of each part and the number of extra nodes**\n    - Use integer division and the modulus operation to calculate:\n      - `part_size`: the base size of each part, which is `count // k`.\n      - `extra_nodes`: the number of parts that should have one extra node, which is `count % k`.\n\n3. **Step 3: Split the linked list into `k` parts**\n    - Reset `current` to `head` to start splitting the list.\n    - Initialize an empty list `result` to store the head of each part.\n    - Loop through `k` iterations to create each part:\n      - For each part, set `part_head` to the `current` node, which is the starting node of that part.\n      - Determine how many nodes this part should contain: `part_size + 1` if this part is one of the first `extra_nodes` parts (i.e., `i < extra_nodes`), otherwise `part_size`.\n      - Move the `current` pointer `part_size - 1 + (i < extra_nodes)` times to reach the last node of the part.\n      - If `current` is not `None`, detach this part from the rest of the list by setting the `next` pointer of the last node to `None`, and move the `current` pointer to the next node (`next_node`).\n      - Append `part_head` to the `result` list.\n\n4. **Step 4: Return the result**\n    - After constructing all `k` parts, return the `result` list, which contains the heads of the split parts.\n    - If `k` is greater than the number of nodes in the list, some parts in the result will be `None`.\n\n### Time Complexity:\n- Traversing the entire list takes `O(n)`, where `n` is the number of nodes in the list.\n- Splitting the list into `k` parts also takes `O(n)`, since each node is visited once.\n- Therefore, the overall time complexity is `O(n)`.\n\n### Edge Cases:\n- If `k` is greater than the number of nodes, some parts will be `None`.\n- If `head` is `None` (an empty list), the function returns `k` parts, all of which are `None`.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']