Shared my AC C++ code - with explanations, hopefully understandable


  • 0
    R

    The idea is consider the block of k nodes, and reverse each block, also keep track of the node previous to each block(pre in the code), then when reversed is done, link the previous node to the start of the reversed block

    class Solution {
        public:
            ListNode* reverseKGroup(ListNode* head, int k) {
                ListNode* dummy=new ListNode(1), *cur=head, *pre=dummy, *next, *nextPre;
                dummy->next=head; 
                int count=0;
                while(cur!=NULL){
                    next=cur->next;
                    count++;
                    if(count==k){
                        nextPre=pre->next;
                        pre->next=reverse(pre->next, cur->next); 
        		        pre=nextPre;
                        count=0;
                    }
                    cur=next;
                }
                head=dummy->next; delete dummy;
                return head;
            }
        private:
            /* reverse the linked list from start up to the node after, 
               return back the new head, and link the end of the block to the node after */
            ListNode* reverse(ListNode* start, ListNode* after) {
                ListNode* newEnd=start;
                ListNode* pre=start, *cur=start->next, *next;
                while(cur!=after){
                    next=cur->next;
                    cur->next=pre;
                    pre=cur;
                    cur=next;
                }
             	start->next=after;
                return pre;
            }
        };

Log in to reply
 

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