C++ code with comments - O(n) time


  • 0
    V
    class Solution {
    public:
        vector<ListNode*> splitListToParts(ListNode* root, int k) {
            int len = 0;
            vector<ListNode *> ans;
            ListNode *tmp = root, *prev = NULL;
            while (tmp) { // compute the length of list
                len++;
                tmp = tmp->next;
            }
            int share = len / k; // each part must have these many nodes
            int left = len % k; // remaining nodes to be distributed 1 each from L to R
            tmp = root;
            while (k-- > 0) {
                int sh = share;
                ans.push_back(tmp); // add head of sublist to answer
                while (tmp && sh-- > 0) { // traverse the share
                    prev = tmp;
                    tmp = tmp->next;
                }
                if (left > 0 && tmp) { // include 1 node if remaining
                    prev = tmp;
                    tmp = tmp->next;
                    left--;
                }
                if (prev)
                    prev->next = NULL; // break the list
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.