C++ constant space and iterative approach, easy to understand, a little long than recursive


  • 0
    L

    Code below with comments inline. Variable name should be straight forward.

    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == NULL || head ->next == NULL || k <= 1) { return head; } // cannot reverse
        int len = GetLen(head);
        if(len < k) { return head; } // we cannot reverse due to shorter length
        ListNode* firsthead=head;
        ListNode* prevhead=head; // the previous head will become a later tail
        ListNode* prevtail = head; // when reverse the curr head will become prevtail
        for(int i=0; i < len/k; ++i) {
            
            // following is to do the real reverse
            ListNode* prev=NULL; // previous node before curr
            ListNode* curr=prevhead; // curr node needs to be reversed
            ListNode* after=NULL; // curr->next
            int origk = k;
            while((--origk) >= 0 && curr != NULL) {
                after = curr->next;
                curr->next = prev;
                prev = curr;
                curr = after;
            }
            // prev is the head after current round of reverse
            if( i > 0) { prevtail->next = prev;  }
            prevtail = prevhead; // update the lasttail and prevhead
            prevhead = after; 
            if(i == 0) { firsthead = prev; }
        }
        
        // do the rest:
        if( (len/k)*k < len) {
            prevtail->next = prevhead;
        }
        
        return firsthead; // the root
    }
    
    int GetLen(ListNode* node) {
        int len=0;
        ListNode* x = node;
        while(x != NULL) { ++len; x=x->next; }
        return len;
    }

Log in to reply
 

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