3 C++ codes split Linked List||w Example
Intuition\n Describe your first thoughts on how to solve this problem. \nUse 2 times transversals.\nThe first time to compute n the length for listed list head.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse 2 times transversals.\nThe first time to compute ```n``` the length for listed list head.\nAnd then decide the split linked list ```ans[i]``` should be of length ```iLen[i]```.\n\nSuppose ```auto [q, r]=div(n, k);```\nThe first ```r``` values for ```ans[i]``` (0<=i<r) should be ```q+1``` and the each one of the rest is ```q```.\n\nThe second time for transversal completes the job. Don\'t forget removing the link between split linked lists.\n\nThe 3rd solution attempts to process only the head and tail of ```ans[i]``` on the second pass, but requires more memory, i.e. an array.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDuring the 2nd transversal, proceed for i-th linked list ```ans[i]```\n```\n            while(j<iLen[i]){\n                prev=curr;\n                curr=curr->next;\n                j++;\n            }\n```\nTo split the linked list, one needs an extra pointer ```prev``` or ```last```. Where the place it should split, remove the link \n```\nprev->next=NULL;//Remove the link\n```\nConsider the testcase ```head=[1,2,3,1,2,3,1,2,3,2,2,3,5], k=5```\nThe result is as follows\n```\nn=13 ,q=2 ,r=3\n0:[1->2->3]\n1:[1->2->3]\n2:[1->2->3]\n3:[2->2]\n4:[3->5]\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n+k)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(k)\\to O(k+n)$$\n# Code\n```\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    {\n        ListNode* curr=head;\n        int n=0;\n        while(curr){\n            curr=curr->next;\n            n++;\n        }\n        auto [q, r]=div(n, k);\n        vector<int> iLen(k, q);\n        for (int i=0; i<r; i++)\n            iLen[i]++;\n        vector<ListNode*> ans(k);\n        curr=head;\n        for(int i=0; i<k; i++){\n            ans[i]=curr;\n            int j=0;\n            ListNode* prev=NULL;//extra pointer is needed\n            while(j<iLen[i]){\n                prev=curr;\n                curr=curr->next;\n                j++;\n            }\n            if (prev)\n                prev->next=NULL;//Remove the link\n        }\n        return ans;\n    }\n};\n```\n# 2nd Code with slight Optimization\n```\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) \n    {\n        ListNode* curr=head;\n        int n=0;\n        while(curr){\n            curr=curr->next;\n            n++;\n        }\n        auto [q, r]=div(n, k);\n       \n        vector<int> iLen(k, q);\n        fill(iLen.begin(), iLen.begin()+r, q+1);//Use fill\n        vector<ListNode*> ans(k);\n        curr=head;\n        for(int i=0; i<k; i++){\n            ans[i]=curr;\n            for (int j=0; j < iLen[i]-1; j++) {\n                curr=curr->next;\n            }\n            if (curr) { //Check if curr is not null\n                ListNode* prev=curr; //extra pointer is needed\n                curr=curr->next;\n                prev->next=NULL; //Remove the link\n            }\n        }\n        return ans;\n    }\n};\n```\n# 3rd Code using more memory only dealing with the heads & tails for ans[i]\n```\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) \n    {\n        vector<ListNode*> node;\n        ListNode* curr = head;\n        node.push_back(curr);\n        int n=0;\n        while (curr) {     \n            curr=curr->next;\n            node.push_back(curr);\n            n++;\n        }\n\n        auto [q, r]=div(n, k);\n       \n        vector<int> iLen(k, q);\n        fill(iLen.begin(), iLen.begin()+r, q+1);\n        vector<ListNode*> ans(k, {});\n        int beginIdx=0, endIdx;\n        \n        //Consider only the heads & tails for ans[i]\n        for (int i=0; i<k; i++) {\n            beginIdx=(i==0) ? 0:beginIdx+iLen[i-1];\n            endIdx=(iLen[i]==0)?beginIdx:beginIdx+iLen[i]-1;\n            ans[i]=node[beginIdx];\n            ListNode* last = node[endIdx];\n            if (last) \n                last->next = NULL; // Remove the link\n        }       \n        return ans;\n    }\n};\n\n```
['C++']