Split Linked List in Parts || DCC 08/09/24 || Easy Approach || 90% Beats🔥🔥
Intuition\n- The goal is to split the given singly linked list into k parts such that the length of each part is as equal as possible. This means that the diffe
# Intuition\n- The goal is to split the given singly linked list into k parts such that the length of each part is as equal as possible. This means that the difference in length between any two parts should not be more than one. If there are extra nodes after distributing the nodes equally, these extra nodes should be distributed among the earlier parts.\n\n# Approach\n**Calculate the Length of the Linked List:**\n- First, traverse the linked list to determine its total length, n. This will help in determining how many nodes each part should have.\n\n**Determine the Size of Each Part:**\n- The base size of each part can be calculated as `n / k`. There might be some remainder when dividing, which represents the extra nodes that should be distributed among the first few parts. The remainder is calculated as `n % k`.\n\n**Split the List:**\n- If k is greater than or equal to n, each part will contain exactly one node, and the remaining parts (if any) will be null.\n- If k is less than n, we iterate over the list and split it into k parts. Each part will initially have `n / k` nodes, and for the first `n % k` parts, we add one extra node.\n\n**Form the Parts:**\n- For each part, traverse the necessary number of nodes, detach the part from the main list, and store the head of this part in the result array.\n\n**Return the Result:**\n- Finally, return the array of parts\n\n# Complexity\n**Time complexity:** $$O(n + k)$$\n- The linked list is traversed once to calculate its length, which takes $$O(n)$$ time.\nSplitting the list into k parts takes $$O(n)$$ time as well since we traverse each node exactly once to split it.\n\n**Space complexity:** $$O(k)$$\n- The space complexity is primarily due to the array ans that stores the heads of the k parts. This requires $$O(k)$$ space.\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\n    int LLsize(ListNode* head){\n        ListNode* temp= head;\n        int count=0;\n        while(temp){\n            count++;\n            temp=temp->next;\n        }\n        return count;\n    }\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        vector<ListNode*> ans;\n        \n        int size=LLsize(head);\n        int target= size/k;\n        int rem= size%k;\n\n        if(k>=size){\n            while(size){\n            ListNode* nextN= head->next;\n            head->next=NULL;\n            ans.push_back(head);\n            head= nextN;\n            size--;\n            k--;\n            }\n            while(k){\n                ans.push_back(NULL);\n                k--;\n            }\n            \n        }\n\n        else{\n        while(k){\n          ListNode* curr=head;\n          int pos=target;\n\n          while(pos!=1){\n            curr=curr->next;\n            pos--;\n          }\n          if(rem>0){\n            curr=curr->next;\n            rem--;\n          }\n          ListNode* nextN=curr->next;\n          curr->next=NULL;\n          ans.push_back(head);\n          head= nextN;\n          k--;\n        }\n        }\n        return ans;\n    }\n};\n```
['Linked List', 'C++']