Transparent C++ solution, 4ms, one-pass, O(n)


  • 0
    X
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        n = n - m + 1;
        ListNode* prev = NULL;
        ListNode* current = head;
        while(--m && current)
        {
            prev = current;
            current = current->next;
        }
        
        ListNode* s = prev; /* remember the (m - 1)-th element */
        ListNode* s2 = current; /* remember the m-th element */
        ListNode* next;
        
        /* reverse the linked list between m-th and n-th element as usual */
        while(n && current) 
        {
            --n;
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        
        /* now rearrange the (m-1)-th element to point to the n-th element */
        if(s) s->next = prev;
        /* and rearrange the m-th element to point to the (n + 1)-th element */
        if(s2) s2->next = current;
    
        /* did we have (m-1)-th element, if yes, then it'll be the head, if not, then the last reversed element will be the head */
        return s ? head : prev;

Log in to reply
 

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