C/C++ solution:


  • 0
    M
        ListNode* reverseBetween(ListNode* head, int m, int n) {
            
            if(head == NULL || m == n) return head;
            
            // three parts - (1) head to m-1  (2) m to n  (3) n+1 to end.
            
            //need to save first part's tail element.
            ListNode* ftail = head;
            int i = m-2;
            while(i-- > 0) ftail = ftail->next;
                
            // reverse the second part using 3 pointers method.
            ListNode* p1 = NULL, *p2 = NULL, *p3 = NULL;
            if(m == 1) p1 = head;
            else p1 = ftail->next;
            for(i = m; i <= n; i++)
            {
                p2 = p1->next;
                p1->next = p3;
                p3 = p1;
                p1 = p2;
            }
            
            if(m == 1) //if no part1, connect head to part2
            {
                head->next = p1;
                head = p3;
            }
            else
            {
                //now connect part1 tail with part2 and part2 with part3 head.
                ftail->next->next = p1;
                ftail->next = p3;
            }
            
            return head;
            
        }
    

Log in to reply
 

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