My non-recursive solution


  • 1
    S

    Reverse it in every k groups. There is a condition that

    If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

    So, I need to reverse the final groups twice to make it in order.

    class Solution {
    public:
        ListNode *reverseKGroup(ListNode *head, int k) {
            if (k == 1) return head;
            ListNode * dummy = new ListNode(-1), *tnode = head, *pnode, *cnode;
            ListNode * start;
            int count;
            dummy->next = head;
            start = pnode = dummy;
            while (tnode != NULL){
                count = 0;
                while (tnode != NULL && count < k){
                    cnode = tnode;
                    tnode = tnode->next;
                    cnode->next = pnode;
                    pnode = cnode;
                    count++;
                }
                if (count < k){
                    for (int i = 0; i < count; ++i){
                        pnode = cnode->next;
                        cnode->next = tnode;
                        tnode = cnode;
                        cnode = pnode;
                    }
                    break;
                }
                pnode = start->next;
                start->next->next = tnode;
                start->next = cnode;
                start = pnode;
            }
            return dummy->next;
        }
    };

Log in to reply
 

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