simple C++ recursive O(1) space, O(n) time


  • 0
    V
    ListNode* reverseKGroup(ListNode* head, int k, ListNode* prev = NULL) {
            if (k == 1) return head;
    
            // if there is k left yet
            if (!isEnough(head, k)) {
                if (prev != NULL) prev->next = head;
                return head;
            }
            
            // actual reverse
            ListNode* cur = head;
            int n = k;
            while(n-- && cur)
            {
                ListNode* curnext = cur->next;
                cur->next = prev;
                prev = cur;
                cur = curnext;
            }
            
            //got to assign next to head returned from next part
            head->next = reverseKGroup(cur, k, head);
            
            return prev;
            
        }
        
        bool isEnough(ListNode* cur, int k)
        {
            int n = k;
            int enough = 1;
            while(n--)
            {
                if (cur == NULL)
                {
                    enough = 0;
                    break;
                }
                cur = cur->next;
            }
            return enough;
        }
    

Log in to reply
 

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