4ms C Solution O(n) time and O(1) space


  • 7
    Y

    Use a scout pointer to scan ahead. Once scout has passed k nodes, reverse this chain of k nodes just passed by scout. Initially, both first and current point to the beginning node of this chain. As each node in the chain following current is placed to the beginning of the chain, first is adjusted to always point to the beginning of the chain, while current moves down the chain (since nodes are placed before it). (k-1) nodes need to be moved during each chain reversing. The reversed chain is connected to the previous node (which always points to the one node before the just reversed chain). current (which points to the end of the chain now) is moved forward to the place of scout, count is reset to 0, and scout can now resume scanning forward. : )

    struct ListNode* reverseKGroup(struct ListNode* head, int k) {
        
        struct ListNode *current, *previous, *scout;
        int count;
        
        scout = current = head;
        previous = NULL;
        count = 0;
    
        while (scout) {
            
            ++count;
    
            if (k > 1 && count == k) {
                
                scout = scout->next;
                struct ListNode *first, *following;
                first = current;
                
                while (count-- > 1) {
                    
                    following = current->next;
                    current->next = following->next;
                    following->next = first;
                    first = following;
                }
                
                if (previous)
                    previous->next = first;
                else
                    head = first;
                    
                previous = current;
                current = scout;
                count = 0;
            }
            else
                scout = scout->next;
        }
        
        return head;
    }

  • 0
    N

    Same code took 26 ms in C++ any reason why ?
    What would be time complexity ?


Log in to reply
 

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