Reverse Linked List II

题目：

Reverse a linked list from position m to n. Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

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

分析：

要不停的带入例子去看，不然就会出错，还要考虑m == n

解法：

public class Solution {
    /**
     * @param ListNode head is the head of the linked list 
     * @oaram m and n
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        while (head.next != null) {
            ListNode newhead = head.next;
            head.next = newhead.next;
            newhead.next = dummy.next;
            dummy.next = newhead;
        }
        return dummy.next;
    } 

    public ListNode reverseBetween(ListNode head, int m , int n) {
        // write your code
        if (head == null || head.next == null || m == n) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prevM = dummy;
        ListNode prevN = dummy;
        for (int i = 0; i < m - 1; i++) {
            prevM = prevM.next;
        }
        for (int i = 0; i < n - 1; i++) {
            prevN = prevN.next;
        }

        ListNode M = prevM.next;
        prevM.next = null;

        ListNode nextN = prevN.next.next;
        prevN.next.next = null;

        M = reverseList(M);
        prevM.next = M;
        while (M.next != null) {
            M = M.next;
        }
        M.next = nextN;

        return dummy.next;
    }
}