Reverse a linked list from position m to n. Do it in one-pass.

Example：

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Note：

1 ≤ m ≤ n ≤ length of list.

解釋下題目：

在一次循環(huán)中把鏈表指定位置倒序

1. 老實倒序

實際耗時：3ms

public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        ListNode fakeHead = new ListNode(0);
        fakeHead.next = head;
        ListNode pre = fakeHead;
        for (int i = 0; i < m - 1; i++) {
            //不停移動pre  直到pre到達要開始逆序的之前的那個數(shù)
            pre = pre.next;
        }

        //start指向將要換的那個數(shù)  nex指向start的下一個數(shù)
        ListNode start = pre.next;
        ListNode nex = start.next;

        //開始執(zhí)行n-m次
        for (int i = 0; i < n - m; i++) {
            start.next = nex.next;
            nex.next = pre.next;
            pre.next = nex;
            nex = start.next;
        }

        return fakeHead.next;

    }

??思路很難說，直接上個交換的順序自己感受下：

1->3->2->4->5->6->7->8->9
1->4->3->2->5->6->7->8->9
1->5->4->3->2->6->7->8->9
1->6->5->4->3->2->7->8->9
1->7->6->5->4->3->2->8->9
1->8->7->6->5->4->3->2->9

??可以發(fā)現(xiàn)的一點是，最開始要交換的這個數(shù)到最后肯定是到最后的。我一開始被這個卡住了。還有注意的是交換的斜對角線原則。就沒什么問題了。

時間復雜度O(m-n)

空間復雜度O(1)