Reverse Linked List II

题目：

Reverse a linked list from position m to n.

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

分析：

按照正常思路去写，记得找到m - n这一段之后要把他们的首尾断开。

解法：

class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @param m: The start position need to reverse.
     * @param n: The end position need to reverse.
     * @return: The new head of partial reversed linked list.
     */

    ListNode* reverseList(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        while (head->next != NULL) {
            ListNode* next = head->next;
            head->next = next->next;
            next->next = dummy.next;
            dummy.next = next;
        }
        return dummy.next;
    } 

    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // write your code here
        if (head == NULL || head->next == NULL) {
            return head;
        }

        if (m == n) {
            return head;
        }

        ListNode dummy(0);
        dummy.next = head;

        ListNode* prevM = &dummy;
        ListNode* nextN = &dummy;

        for (int i = 0; i < m - 1; i++) {
            prevM = prevM->next;
            nextN = nextN->next;
        }

        for (int i = 0; i < n - m + 1; i++) {
            nextN = nextN->next;
        }

        ListNode* sectionHead = prevM->next;
        prevM->next = NULL;
        ListNode* sectionTail = nextN->next;
        nextN->next = NULL;

        prevM->next = reverseList(sectionHead);
        while (prevM->next != NULL) {
            prevM = prevM->next;
        }
        prevM->next = sectionTail;

        return dummy.next;
    }
};