C++ in 14 lines


  • 11
    L
    class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) {
            ListNode dummy(0);
            dummy.next = head;
            ListNode *slow = &dummy;
            n -= m;
            while (--m)
                slow = slow->next;
            ListNode *fast = slow->next, *tmp;
            while (n--) {
                tmp = fast->next;
                fast->next = fast->next->next;
                tmp->next = slow->next;
                slow->next = tmp;
            }
            return dummy.next;
        }
    };

  • 5
    H

    Nice solution! I want to add some explanations to make it more comprehensive. The solution reverses elements within the range [m, n] one by one. The slow and fast pointers never move. "slow“ stays one element before the beginning and ”fast“ stays at the end of the reversed part. "tmp" is used to point to the element that will be moved from the end to the beginning in each iteration, it is the only pointer that moves. With #(n-m) iterations, we get the result.

    This example shows how the list changes in each iteration and pointer status after it:

    Input 1->2->3->4->5->6, m = 2, n = 5

    1. 1->3->2->4->5->6, slow@1, fast@2, tmp@3
    2. 1->4->3->2->5->6, slow@1, fast@2, tmp@4
    3. 1->5->4->3->2->6, slow@1, fast@2, tmp@5

    The same Java code:

       public class Solution {
            public ListNode reverseBetween(ListNode head, int m, int n) {
                ListNode dummy = new ListNode(0);
                dummy.next = head;
                ListNode slow = dummy;
                n = n - m;
                while (--m > 0) slow = slow.next;
                ListNode fast = slow.next, tmp;
                while (n > 0) {
                    tmp = fast.next;
                    fast.next = fast.next.next;
                    tmp.next = slow.next;
                    slow.next = tmp;
                    n--;
                }
                return dummy.next;
            }
        }

Log in to reply
 

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