Reverse Linked List II

Reverse a linked list from position m to n.

http://www.lintcode.com/en/problem/reverse-linked-list-ii/

Discussion

找到第m个node，记录下来(start)，前面一个node也记录下来(preStart)，开始翻转直到第n个node，这时候要把翻转开始的start和prestart两个node和翻转结束的时候的node end和afterEnd两个nodes的关系建立起来。

Solution

    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *prev = &dummy;
        ListNode *cur = &dummy;
        for(int i=0; i<m; i++) {
            prev = cur;
            cur = cur->next;
        }
        ListNode *start = cur;
        ListNode *pre_start = prev;
        for(int i=m; i<=n; i++) {
            ListNode *nt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nt;
        }
        pre_start->next = prev;
        start->next = cur;
        return dummy.next;
    }