Simple C++ Solution with commnets O(N)


  • 0
    L
    class Solution {
    public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {             
        // Find the length of the List
        ListNode *temp = root;
        int listLen = 0;
        while(temp){
            ++listLen;
            temp = temp->next;
        }
        
        // Calculate the number of nodes each list should have
        vector<int> nNodes(k,listLen/k);
        int remain = listLen % k;
        for(int i=0; i < remain; ++i) 
            nNodes[i] += 1;
    
        
        // Let's add lists into vector. Initialize all the lists with nullptr
        vector<ListNode*> result(k, nullptr);
        for(int i=0; i<k; ++i){
            temp = root;
            result[i] = temp;
            if(temp){
                // move the temp ahead till we get to the last Node for this sub-list
                // nNodes[i] - 1 because last node's information we need for next list
                for(int j=0; j < nNodes[i]-1; ++j){
                    temp = temp->next;
                }
                // update root for next iteration
                root = temp->next;
                // End this sub-list
                temp->next = nullptr;
            }
        }
        return result;
    }
    };

Log in to reply
 

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