C++ solution with detailed explanation. code as readable as natural language


  • 0

    This solution sacrifices the succinctness of the code for maximal readability. The idea is: As we reverse the list, there are essentially four ends to keep track of: the tail of the front part, the head and tail of the reversed list, and the head of the rear part. So I make these states explicit in the following code.
    For example, for 1->2->3->4->5->NULL with m = 2 and n = 4, in the end frontTail will be pointing to 1, reverseHead to 4, reverseTail to 2 and rearHead to 5.
    When we reverse the list, at each iteration we update the states in the following way:

    • reverseHead becomes rearHead
    • rearHead becomes its next element
    • rearHead's next element becomes the new reverseHead

    In the end just connect the front part with the reversed list and the reversed list with the rear part. The fakeHead is just a trick to handle a special case like other solutions do.

        ListNode* reverseBetween(ListNode* head, int m, int n) {
            ListNode* fakeHead = new ListNode(0);
            fakeHead->next = head;
            ListNode* frontTail = fakeHead;
            for (int i = 1; i < m; i++)
                frontTail = frontTail->next;
            if (!reverseTail->next)
                return head;
            // keeping track of the head and tail of the reversed list: reverseHead and reverseTail
            // keeping track of the tail of the front end and the head of the back end: frontTail and rearHead
            // initially, frontTail is pointing to the m - 1 position, reverseTail the m position
            // rearHead is pointing to the m + 1 position and reverseHead the m position
            // As we start reversing the list from m to n, rearHead and reverseHead advance,
            // while frontTail and rearTail stay unchanged. In the end, connect rearTail with reverseTail
            // and frontTail with reverseHead
            ListNode* reverseTail = frontTail->next;
            ListNode* reverseHead = reverseTail;
            ListNode* rearHead = reverseTail->next;
            for (int i = 0; i < n - m; i++) {
                ListNode* tmp = rearHead->next;
                rearHead->next = reverseHead;
                reverseHead = rearHead;
                rearHead = tmp;
            }
            reverseTail->next = rearHead;
            frontTail->next = reverseHead;
            return fakeHead->next;
        }
    

Log in to reply
 

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