Simple C++ with Explanation


  • 1

    Find the size of the linked list and store that in n. Divide n by k to find out the size of each individual linked list chunk of the original linked list. leftover is the remainder of n/k and is > 0 when n is NOT evenly divisible by k. These leftovers are evenly distributed one at a time onto the end of each of the linked list chunks (starting at the beginning, not all chunks may be modified ). If a chunk contains a leftover then that chunk size is a usual chunk size plus 1. Otherwise, the usual chunk size is used. Then iterate through the linked list, keeping track of the head of each chunk, using prev to follow curr in order to set the last LinkNode's next pointer to nullptr and keep track of where the next iteration of the original linked list should re-occur. Push each head of each chunk into the vector res, which is the result to be returned. Lastly for the corner case ( my one bug which cost me 5 minutes time in this contest ) if k is larger than n, then append empty linked lists onto the end of res.

    class Solution {
    public:
        vector<ListNode*> splitListToParts(ListNode* root, int k) {
            vector<ListNode*> res;
            int n=0,chunk=0,leftover=0;
            ListNode* itr=root;
            while(itr){
                ++n;
                itr=itr->next;
            }
            chunk=n/k;
            leftover=n%k;
            itr=root;
            while(itr){
                int size=leftover-- > 0 ? chunk+1 : chunk;
                ListNode *head=itr, *prev=nullptr, *curr=itr;
                while(size){
                    prev=curr;
                    curr=curr->next;
                    --size;
                }
                prev->next=nullptr;
                itr=curr;
                res.push_back(head);
            }
            while (k>n){
                res.push_back(nullptr);
                --k;
            }
            return res;
        }
    };
    

    More concise solution: initialize the vector with k nullptrs

    class Solution {
    public:
        vector<ListNode*> splitListToParts(ListNode* root, int k) {
            vector<ListNode*> res(k,nullptr);
            int n=0,chunk=0,leftover=0;
            ListNode* itr=root;
            while(itr){
                ++n;
                itr=itr->next;
            }
            chunk=n/k;
            leftover=n%k;
            itr=root;
            for (int i=0; itr; ++i){
                int size=leftover-- > 0 ? chunk+1 : chunk;
                ListNode *head=itr, *prev=nullptr, *curr=itr;
                for (int j=0; j<size; ++j){
                    prev=curr;
                    curr=curr->next;
                }
                prev->next=nullptr;
                itr=curr;
                res[i]=head;
            }
            return res;
        }
    };
    

  • 1
    D

    @claytonjwong I wound up with the same approach -- and the same mistake costing me 5 minutes!


  • 1

    I hear you @dcmeserve I just added on a more concise version above with initializes the vector with size k. That way, there's no way to forget doing that at the end. What do you think? Thanks again for your feedback!


  • 0
    D

    @claytonjwong

    Oh, yes, of course! That's a much better idea.

    Here's mine, with that idea integrated. The only other real difference is that I used a single loop for the splitting instead of nested:

    class Solution {
    public:
        vector<ListNode*> splitListToParts(ListNode* root, int k) {
            vector<ListNode*> partRoots(k,NULL);
            int length = 0;
            for( ListNode *n=root ; n ; n = n->next ) ++length;
            int partLen = length / k;
            int leftover = (length % k);
            int iPartMember = 0;
            int iPartRoot = 0;
            ListNode *prev = NULL;
            for( ListNode *n=root ; n ; n = n->next ) {
                if (iPartMember == 0) {
                    partRoots[iPartRoot] = n;
                    if (prev) prev->next = NULL;
                    ++iPartRoot;
                }
                ++iPartMember;
                if (iPartMember == partLen + (leftover>0?1:0)) {
                    iPartMember = 0;
                    --leftover;
                }
                prev = n;
            }
            return partRoots;
        }
    };
    

    (I also improved some of the var names for readability, including borrowing your name "leftover".)


Log in to reply
 

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