Single pass O(n) solution with no extra space.


  • 0
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     *
     * Always reverse k nodes, for the first set of k nodes modify the head to be returned
     * From the second set of k nodes onwards, we need to point the head of previous 
     * set of k nodes to the head of the current reversed set of k nodes.
     * The last set may or may not have k nodes.
     * reverse k or whatever possible, incase not k then reverse it back!!:)
     * 
     * 
     **/
    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            ListNode *curr = head,*prev=NULL, *next=NULL,*head_sub,*head_sub_prev=NULL;
            int first_flag  = 0;
            while(curr)
            {
                int count       = 0;
                head_sub        = curr;
                prev            = NULL;
                while((count < k)  && (curr!=NULL))
                {
                    next        = curr->next;
                    curr->next  = prev;
                    prev        = curr;
                    curr        = next;
                    count++;
                }
                
                if(count == k)
                {
                    if(head_sub_prev)
                        head_sub_prev->next = prev;
                        
                    head_sub->next          = curr;
                    head_sub_prev           = head_sub;
                    
                    if(!first_flag)
                    {
                        first_flag          = 1;
                        head                = prev;
                    }
                }
                else
                {
                    //reverse back remaining nodes incase not a multiple of k;
                    curr = prev;prev=NULL;
                    count = 0;
                    while((count < k)  && (curr!=NULL))
                    {
                        next                = curr->next;
                        curr->next          = prev;
                        prev                = curr;
                        curr                = next;
                        count++;
                    }
                }
            }
            
            return head;
        }
    };
    
    

Log in to reply
 

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