Concise O(n) solution, one pass


  • 0
    S
        // one pass, O(n) solution
        // (head)p1 || --> p2 --> * --> p3(p1) --> || --> p2 --> * --> p3(p1) --> || --> * --> NULL    
        ListNode *reverseKGroup(ListNode *head, int k) {
            if (!head || k <= 1) return head;
            // p1 point to the node before (0, ..., k-1) segment
            // p2, q point to the first node in (0, ..., k-1) segment, p2 will travel in the process
            // p3 point to the last node in (0, ..., k-1) segment
            ListNode *p1 = head, *p2 = head, *p3 = head;
            ListNode *q = head, *tmp = NULL;
            
            while (1) {
                // set p3 to the k'th node
                int i = 1;
                while (i < k && p3) {
                    p3 = p3->next; ++i;
                }
                if (i != k || !p3) break;
                
                while (p2 != p3) {
                    tmp = p2->next;
                    p2->next = p3->next;
                    p3->next = p2;
                    p2 = tmp;
                }
                
                if (q == head) head = p2;
                else p1->next = p2;
                
                p1 = q;
                p3 = p2 = q = q->next;
            }
            
            return head;
        }

Log in to reply
 

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