My one pass, in place solution in C++


  • 0
    M

    In the given problem, instead of swapping the nodes, we can just swap the data. As we are given a singly linked list, we need to travel till the target node.

    Here is my code:

        ListNode *reverseBetween(ListNode *head, int m, int n) {
                if(!head || !head->next || m==n)
                    return head;
        
                int m1=m,n1=n;
                ListNode* left=head;
                // travelling till we mark the range nodes.
                while(--m){
                    left=left->next; 
                    --n;
                }
        
                ListNode* right=left;
               // instead of traveling from beginning for end marker we can can use start position of range
                while(--n){
                    right = right->next;
                }
        
                m = m1;
                n = n1;
                while(m1<n1){
                    swap(left->val,right->val);
                    ++m1;
                    --n1;
                    left = left->next;
    /*after swapping data we can increment start marker and decrease end marker*/
    /*but as we cannot move back, we have to again travel from start marker to point the new end marker*/
                    int temp1 = ++m;
                    int temp2 = --n;
                    ListNode *travel = left;
                    while(temp1 < temp2){
                        travel = travel->next;
                        ++temp1;
                    }
                    right = travel;
                }
    
            return head;
        }

  • 0
    M
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(m>=n) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        int s = m;
        // get to the start point
        while(--s){ 
            dummy = dummy->next;
            --n;
        }
        ListNode *p1 = dummy->next;
        ListNode *p2 = p1->next;
        ListNode *p3;
        //start reverse
        while(--n){
            p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
        dummy->next->next = p2; //link to the left part
        dummy->next = p1; //link to new beginning
        if(m==1) return dummy->next; // head has changed, reference by dummy
        return head;
    }

Log in to reply
 

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