Accepted non-recursive C++ solution


  • 0
    C

    O(n) and O(1) of course it is.

    Each time when starting, find the future new head (nh) and save the old head of the next to-be-reversed list. If existed, nh is k step far from oh. Then reverse the list from oh to nh and save its tail for combination.

    Example:

    1-2-3-4-5

    iter1: oh = 1, nh = 2 2-1-3-4-5

    iter2: oh = 3, nh = 4 2-1-4-3-5

    iter3: oh = 5, nh = 0 2-1-4-3-5

        ListNode *reverseKGroup(ListNode *head, int k) {
        if(!head || !head->next || k==1) return head;
        int i=k;
        ListNode * p0 = head, * p1 = head->next, * p2 = 0, * t = 0, * ret = head, *oh, * nh;
        while(p1)
        {
            oh = nh = p0;
            i = k;
            while(--i && nh)
                nh = nh->next;
            if(!nh) break;
            i = k;
            while(--i)
            {
                p2 = p1->next;
                p1->next = p0;
                p0 = p1;
                p1 = p2;
            }
            if(t)
                t->next = p0;
            else
                ret = p0;
            p0 = oh;
            t = p0;
    
            p0 = p0->next = p1;
            if(p1)
                p1 = p1->next;
        }
        return ret;
    }

Log in to reply
 

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