Sharing both iterative and recursive solution


  • 0
    Z
    ListNode *reverseKGroup(ListNode *head, int k) {
        if(head == nullptr){
            return nullptr;
        }
        if(k == 1){
            return head;
        }
        ListNode* dummyNode = new ListNode(0);
        dummyNode->next = head;
        ListNode* p1 = dummyNode;
        ListNode* p2;
        ListNode* p3;
        while(true){
            p2 = p1;
            bool isContinue = true;
            for(int i = 0; i < k; i++){
                p2 = p2->next;
                if(p2 == nullptr){
                    isContinue = false;
                    break;
                }
            }
            if(!isContinue){
                break;
            }
            p3 = p2->next;
            ListNode* begin = p1->next;
            ListNode* end = p2;
            reverse(begin, end);
            p1->next = end;
            begin->next = p3;
            p1 = begin;
        }
        return dummyNode->next;
    }
    void reverse(ListNode* head, ListNode* tail){
        tail->next = nullptr;
        ListNode* p1 = head;
        ListNode* p2 = p1->next;
        while(p1 != nullptr && p2 != nullptr){
            ListNode* p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
    }
    

    Above is the iterative one.

    And below is the recursive one.

    ListNode *reverseKGroup(ListNode *head, int k) {
        if(head == nullptr){
            return nullptr;
        }
        if(k == 0 || k == 1){
            return head;
        }
        
        return helper(head, k);
    }
    
    ListNode* helper(ListNode* head, int k){
        if(head == nullptr){
            return nullptr;
        }
        
        ListNode* end = head;
        for(int i = 0; i < k - 1; i++){
            if(end->next != nullptr){
                end = end->next;
            }
            else{
                return head;
            }
        }
        
        end = end->next;
        
        ListNode* p1 = nullptr;
        ListNode* p2 = head;
        ListNode* p3 = head->next;
        
        while(true){
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            p3 = p3->next;
            if(p2->next == end){
                p2->next = p1;
                break;
            }
        }
        
        p1 = p2;
        while(p1->next != nullptr){
            p1 = p1->next;
        }
        
        p1->next = helper(end, k);
        
        return p2;
    }
    

    They are all pretty straightforward. Just do what requirements ask you to do. No tricky part.


Log in to reply
 

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