2. 反转链表中的第m节到第n节

Q: 有一个链表ListNode head, 反转其中的第m节到第n节。
比如 1->2->3->4->5, 反转2到4节。结果是 1->4->3->2->5.

思路

1. 先确定几个位置，如图：

   
   2. 反转链表中的第m节到第n节

2. 将begin 到 end 的这一段进行反转。

3. 用before begin 去连反转后那段的头，用反转后那段的尾巴去连after end.

需要注意的地方：
边界上的反转可能会使链表断开（我写的时候卡在这点上一段时间）。

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode (int val) {
        this.val = val;
    }
}

public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) { return null; }
        ListNode beforeBegin;
        ListNode afterEnd;
        ListNode end;
        ListNode begin; 
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        beforeBegin = dummy;
        for (int i = 0; i < m - 1; i++) {
            beforeBegin = beforeBegin.next;
        }
        begin = beforeBegin.next;
        end = beforeBegin.next;
        for (int i = 0; i < n - m; i++) {
            end = end.next;
        }
        afterEnd = end.next;
        beforeBegin.next = null;
        end.next = null;
        ListNode middle = simpleReverse(begin);
        beforeBegin.next = middle;
        ListNode middleTail = middle;
        while(middleTail.next !=null) {
            middleTail = middleTail.next;
        }
        middleTail.next = afterEnd;
        return dummy.next;
 }

private ListNode simpleReverse(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode cur = head;
        while (cur != null) {
            ListNode ne = cur.next;
            cur.next = prev;
            prev = cur;
            cur = ne;
        }
        dummy.next.next = null;
        return prev;
 }

// create a Linked List for testing
public ListNode createList(int n) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for (int i=1; i<=n; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        return dummy.next;
 }
// Test methdod 
public static void main(String[] args) {
        Test test = new Test();
        ListNode head = test.createList(8);
        ListNode testList = test.reverseBetween(head, 1, 2);
        ListNode cur = testList;
        while(cur!=null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
} 

// Test results
// reverseBetween(head, 1, 2) -> 2 1 3 4 5 6 7 8 
// reverseBetween(head, 1, 8) -> 8 7 6 5 4 3 2 1 
// reverseBetween(head, 1, 1) -> 1 2 3 4 5 6 7 8 
// reverseBetween(head, 8, 8) -> 1 2 3 4 5 6 7 8 
// reverseBetween(head, 2, 7) -> 1 7 6 5 4 3 2 8
// reverseBetween(head, 2, 8) -> 1 8 7 6 5 4 3 2