Beats 100% (Java) | Easy Code |
Intuition\nThe goal is to split a linked list into k parts as equally as possible. Some parts may have one more node than others if the list size is not perfect
# Intuition\nThe goal is to split a linked list into k parts as equally as possible. Some parts may have one more node than others if the list size is not perfectly divisible by k. The approach aims to handle this by distributing the extra nodes across the first few parts.\n\n# Approach\n1. Count the Length of the Linked List: First, traverse the linked list to count the total number of nodes, n.\n\n2. Determine the Sizes of Each Part:\n\n    - Calculate q = n / k: This gives the base size of each part.\n    - Calculate r = n % k: This gives the remainder, which tells how many parts need to have an extra node.\n    - So, the first r parts will have q + 1 nodes, and the remaining k - r parts will have q nodes.\n\n3. Split the List:\n\n    - Traverse the list again, assigning q + 1 nodes to the first r parts, and q nodes to the remaining parts.\n    - For each part, break the link after the designated number of nodes and store the head of the part in the result.\n4. Handle Cases Where k > n: If k is greater than n, there will be some parts that are NULL. These are handled by adding NULL to the result after the list has been fully traversed.\n# Complexity\n- Time Complexity: O(n).\n- Space Complexity:O(k) for storing the k parts in the result vector.\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        int n = 0;\n        ListNode*temp = head,*curr=head;\n\n        while(temp){\n            n++;\n            temp = temp->next;\n        }\n\n        int q = n/k;\n        int r = n%k;\n\n        vector<ListNode*> res;\n\n        temp = head;\n\n        if(k > n){\n            while(temp){\n                res.push_back(curr);\n\n                curr = temp->next;\n                temp->next = NULL;\n                temp = curr;\n                k--;\n            }\n            while(k--) res.push_back(NULL);\n\n            return res;\n        }\n\n        while(k--){\n            res.push_back(curr);\n\n            for(int i=1; i<q;i++){\n                temp=temp->next;\n            }\n            if(r > 0){\n                temp = temp->next;\n                r--;\n            }\n\n            if(temp == NULL) break;\n\n            curr = temp->next;\n            temp->next = NULL;\n            temp = curr;\n        }\n        return res;\n    }\n};\n```\n```Java []\nclass Solution {\n    public ListNode[] splitListToParts(ListNode head, int k) {\n        ListNode[] res = new ListNode[k];\n        int n = 0;\n        ListNode temp = head;\n        \n        // Count the number of nodes in the linked list\n        while (temp != null) {\n            n++;\n            temp = temp.next;\n        }\n        \n        int q = n / k;\n        int r = n % k;\n        \n        ListNode curr = head;\n        for (int i = 0; i < k; i++) {\n            res[i] = curr;\n            int partSize = q + (r > 0 ? 1 : 0); // Add an extra node for first r parts\n            \n            for (int j = 1; j < partSize && curr != null; j++) {\n                curr = curr.next;\n            }\n            \n            if (curr != null) {\n                ListNode next = curr.next;\n                curr.next = null; // Break the link\n                curr = next;\n            }\n            \n            if (r > 0) r--;\n        }\n        \n        return res;\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n        # Calculate the total number of nodes\n        n = 0\n        temp = head\n        while temp:\n            n += 1\n            temp = temp.next\n        \n        q, r = divmod(n, k)\n        \n        res = []\n        curr = head\n        \n        for i in range(k):\n            res.append(curr)\n            part_size = q + (1 if r > 0 else 0)\n            \n            for _ in range(1, part_size):\n                if curr:\n                    curr = curr.next\n            \n            if curr:\n                next_node = curr.next\n                curr.next = None\n                curr = next_node\n            \n            if r > 0:\n                r -= 1\n        \n        return res\n\n```\n```Javascript []\nvar splitListToParts = function(head, k) {\n    let n = 0;\n    let temp = head;\n    \n    // Count the number of nodes\n    while (temp !== null) {\n        n++;\n        temp = temp.next;\n    }\n    \n    const q = Math.floor(n / k);\n    let r = n % k;\n    \n    const result = new Array(k).fill(null);\n    let curr = head;\n    \n    for (let i = 0; i < k; i++) {\n        result[i] = curr;\n        let partSize = q + (r > 0 ? 1 : 0);\n        \n        for (let j = 1; j < partSize && curr !== null; j++) {\n            curr = curr.next;\n        }\n        \n        if (curr !== null) {\n            let next = curr.next;\n            curr.next = null;\n            curr = next;\n        }\n        \n        if (r > 0) r--;\n    }\n    \n    return result;\n};\n\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/a6f7e428-2387-4bd4-9c0e-99e1c5477c94_1725771899.859248.png)\n
['Linked List', 'Python', 'C++', 'Java', 'JavaScript']