✔99.00% Beats C++✨|| Easy to Understand📈😇|| C++|| JAVA|| JAVASCRIPT || PYTHON||GO||#Beginner😉😎
Intuition\n- The problem requires splitting a linked list into k parts of approximately equal size. \n- If k is larger than the number of elements in the list, 
# Intuition\n- The problem requires splitting a linked list into `k` parts of approximately equal size. \n- If `k` is larger than the number of elements in the list, some of the parts will be empty. \n- The goal is to divide the linked list in such a way that the difference in sizes between any two parts is at most 1.\n\n# **Strategies to tackle the problem**\n**1. Count the number of nodes:**\n- Traverse the linked list to count the total number of nodes (`n`).\n\n**2. Calculate the approximate part size:**\n\n- Calculate the approximate size of each part by dividing `n` by `k`. Let\'s call this value `x`.\n\n**3. Initialize pointers:**\n\n- Initialize a pointer `curr` to the head of the linked list to keep track of the current node.\n- Create an empty vector `ans` to store the heads of the split linked lists.\n\n4. Split the linked list into parts:\n\n- Iterate over `k` parts using a loop.\n- For each part:\n   a. Calculate the real size of the part:\n\n- If `i < n % k`, increment realSize by 1 (to distribute the remainder nodes).\n\n  b. If `realSize` is 0, push a `NULL` into `ans` to represent an empty part.\nc. Otherwise, push `curr` (the current head of the part) into `ans`.\nd. Traverse the current part `realSize - 1` times to reach the end.\ne. Update `curr` to point to the next node.\nf. Set the `next` pointer of the last node in the current part to `NULL` to split the part from the rest of the list.\n\n**5. Return the result:**\n\n- After iterating over all parts, return the `ans` vector, which contains the heads of the split linked lists.\n- By following these step-by-step strategies, you can effectively split the linked list into `k` parts while maintaining the balance of nodes in each part.\n\n# Approach\n\n\n1. Traverse the linked list once to count the total number of nodes (`n`).\n1. Calculate the approximate size (`x`) of each part by dividing `n` by `k`.\n1. Initialize a pointer `curr` to the head of the linked list.\n1. Iterate over `k` parts:\na. Calculate the real size of the current part, which is `x`. If `i < n % k`, increment the real size by 1 because these parts should have one extra node to distribute the remainder.\nb. If the real size is 0, push a `NULL` pointer to the result vector to indicate an empty part.\nc. Otherwise, push `curr` (the current head of the part) to the result vector.\nd. Traverse the current part `realSize - 1` times to reach the end of the part.\ne. Update `curr` to point to the next node.\nf. Set the `next` pointer of the last node in the current part to `NULL` to split the part from the rest of the list.\n1. After iterating over all parts, return the result vector containing the heads of the split linked lists.\n\n# Complexity\n- Time complexity:\n1. Counting the number of nodes in the linked list takes O(n) time, where n is the number of nodes in the list.\n1. The loop that splits the list into `k` parts runs in O(k) time.\n1. In each iteration of the loop, we traverse a part of the list. In the worst case, where `k` is equal to the number of nodes `n`, each traversal takes O(n) time.\n1. Therefore, the overall `time complexity` is` O(n + k * n) = O(k * n)`.\n\n- Space complexity:\n1. The space complexity is primarily determined by the space required for the result vector `ans`, which contains the heads of the split linked lists. In the worst case, where `k` is equal to the number of nodes `n`, this vector can contain up to `k` elements.\n1. The space required for the result vector is O(k).\n1. Additionally, the space used for other variables (e.g., `curr`, `realSize`, `temp`) is constant and does not depend on the input size.\n1. Therefore, the overall `space complexity is O(k)`.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        int n=0;\n        ListNode* curr=head;\n        while(curr){\n            n++;\n            curr=curr->next;\n        }\n        \n        vector<ListNode*> ans;\n        int x=n/k;\n        \n        curr=head;\n        for(int i=0;i<k;i++)\n        {\n            int realSize=x;\n            if(i<n%k) realSize++;\n            if(realSize==0)\n            {\n                ans.push_back(NULL);\n                continue;\n            }\n            \n            \n            ans.push_back(curr);\n            \n            for(int j=0;j<realSize-1;j++)\n            {\n                curr=curr->next;\n            }\n            \n            ListNode* temp=curr;\n            curr=curr->next;\n            temp->next=NULL;\n        }\n        \n        \n        return ans;\n    }\n};\n``````\n# JAVA\n```\nclass Solution {\n    public ListNode[] splitListToParts(ListNode head, int k) {\n        int n = 0;\n        ListNode curr = head;\n        while (curr != null) {\n            n++;\n            curr = curr.next;\n        }\n\n        ListNode[] ans = new ListNode[k];\n        int x = n / k;\n\n        curr = head;\n        for (int i = 0; i < k; i++) {\n            int realSize = x;\n            if (i < n % k) {\n                realSize++;\n            }\n            if (realSize == 0) {\n                ans[i] = null;\n                continue;\n            }\n\n            ans[i] = curr;\n\n            for (int j = 0; j < realSize - 1; j++) {\n                curr = curr.next;\n            }\n\n            ListNode temp = curr;\n            curr = curr.next;\n            temp.next = null;\n        }\n\n        return ans;\n    }\n};\n\n```\n# PYTHON\n```\nclass Solution:\n    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:\n        n = 0\n        curr = head\n        while curr:\n            n += 1\n            curr = curr.next\n\n        ans = [None] * k\n        x = n // k\n\n        curr = head\n        for i in range(k):\n            realSize = x\n            if i < n % k:\n                realSize += 1\n            if realSize == 0:\n                ans[i] = None\n                continue\n\n            ans[i] = curr\n\n            for j in range(realSize - 1):\n                curr = curr.next\n\n            temp = curr\n            curr = curr.next\n            temp.next = None\n\n        return ans\n\n```\n# JAVSCRIPT\n```\nclass Solution {\n    splitListToParts(head, k) {\n        let n = 0;\n        let curr = head;\n        while (curr !== null) {\n            n++;\n            curr = curr.next;\n        }\n\n        const ans = new Array(k);\n        const x = Math.floor(n / k);\n\n        curr = head;\n        for (let i = 0; i < k; i++) {\n            let realSize = x;\n            if (i < n % k) {\n                realSize++;\n            }\n            if (realSize === 0) {\n                ans[i] = null;\n                continue;\n            }\n\n            ans[i] = curr;\n\n            for (let j = 0; j < realSize - 1; j++) {\n                curr = curr.next;\n            }\n\n            const temp = curr;\n            curr = curr.next;\n            temp.next = null;\n        }\n\n        return ans;\n    }\n};\n\n```\n# GO\n```\ntype ListNode struct {\n    Val  int\n    Next *ListNode\n}\n\nfunc splitListToParts(head *ListNode, k int) []*ListNode {\n    n := 0\n    curr := head\n    for curr != nil {\n        n++\n        curr = curr.Next\n    }\n\n    ans := make([]*ListNode, k)\n    x := n / k\n    remainder := n % k\n\n    curr = head\n    for i := 0; i < k; i++ {\n        realSize := x\n        if i < remainder {\n            realSize++\n        }\n        if realSize == 0 {\n            ans[i] = nil\n            continue\n        }\n\n        ans[i] = curr\n\n        for j := 0; j < realSize-1; j++ {\n            curr = curr.Next\n        }\n\n        temp := curr\n        curr = curr.Next\n        temp.Next = nil\n    }\n\n    return ans\n};\n\n\n\n
['C++', 'Java', 'Go', 'Python3', 'JavaScript']