4ms solution with c++


  • 0
    Z

    O(N) solution

        ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(m == n)  return head;
        
        ListNode *parent = 0, *p1 = head, *p2 = 0;
        int len = 1;
        
        while(p1 && len < m){
            parent = p1;
            p1 = p1->next;
            len ++;
        }
        
        p2 = p1;
        while(p2 && len < n){
            p2 = p2->next;
            len ++;
        }
        
        if(p1 == 0 || p2 == 0)  return head;
        
        ListNode *left_head = p1, *right_head = p1->next;
        
        ListNode *next = p2->next;
        
        p2->next = 0;
        left_head->next = 0;
        
        while(right_head){
            ListNode *t= right_head->next;
            right_head->next = left_head;
            left_head = right_head;
            
            right_head = t;
        }
        
        p1->next = next;
        
        if(parent == 0){
            head = p2;
        }else{
            parent->next = p2;
        }
        
        return head;
    }

Log in to reply
 

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