反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)。

說(shuō)明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-linked-list-ii

解題思路

首先解決翻轉(zhuǎn)整個(gè)鏈表的問(wèn)題，給定一個(gè)頭節(jié)點(diǎn)，將其所在鏈表翻轉(zhuǎn)
需要有三個(gè)變量來(lái)記錄翻轉(zhuǎn)過(guò)程，pre cur next
分別代表原順序的"上一個(gè)" "當(dāng)前這個(gè)" "下一個(gè)"
現(xiàn)將cur置為頭節(jié)點(diǎn)，pre置為空
當(dāng)cur不為空時(shí)循環(huán)

• 記錄next為cur.next
• cur.next = pre將當(dāng)前節(jié)點(diǎn)的下一個(gè)指向前一個(gè)節(jié)點(diǎn)
• pre = cur
• cur = next 后面兩步起到迭代的作用

循環(huán)結(jié)束時(shí)pre就是新的頭節(jié)點(diǎn)
然后解決翻轉(zhuǎn)一個(gè)鏈表中的一部分
需要將鏈表分為三部分，翻轉(zhuǎn)的前驅(qū)部分，翻轉(zhuǎn)部分，翻轉(zhuǎn)的后繼部分
為了方便處理m = 1也就是從頭結(jié)點(diǎn)開(kāi)始翻轉(zhuǎn)這種情況，使用一個(gè)假的頭結(jié)點(diǎn)dummy
使dummy.next = head
然后從dummy開(kāi)始往后找n次，找到翻轉(zhuǎn)部分的尾節(jié)點(diǎn)，記錄該尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)nextNode，以便翻轉(zhuǎn)后連接上翻轉(zhuǎn)的后繼部分
接著從dummy開(kāi)始往后找m - 1次，找到翻轉(zhuǎn)的前驅(qū)部分的尾節(jié)點(diǎn)并記錄，該節(jié)點(diǎn)的next就是翻轉(zhuǎn)部分的頭節(jié)點(diǎn)
將翻轉(zhuǎn)部分的頭節(jié)點(diǎn)傳給翻轉(zhuǎn)方法，傳遞參數(shù)的頭節(jié)點(diǎn)在翻轉(zhuǎn)后變?yōu)槲补?jié)點(diǎn)，將該節(jié)點(diǎn)的next設(shè)為上述記錄的nextNode
翻轉(zhuǎn)方法返回節(jié)點(diǎn)是翻轉(zhuǎn)后的翻轉(zhuǎn)部分頭節(jié)點(diǎn)，所以翻轉(zhuǎn)的前驅(qū)部分的尾節(jié)點(diǎn)的next設(shè)為該節(jié)點(diǎn)
返回dummy.next

代碼

class Solution {
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        // 輔助頭節(jié)點(diǎn)
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        // 找出要翻轉(zhuǎn)部分的尾節(jié)點(diǎn)
        for (int i = 0; i < n; i++) {
            cur = cur.next;
        }
        // 結(jié)束for后cur是要翻轉(zhuǎn)的尾節(jié)點(diǎn)
        // 保存該節(jié)點(diǎn)的后繼
        ListNode next = cur.next;
        // 斷開(kāi)以便反轉(zhuǎn)
        cur.next = null;
        cur = dummy;
        // for結(jié)束后cur的下一個(gè)是要翻轉(zhuǎn)的部分的頭節(jié)點(diǎn)
        for (int i = 0; i < m - 1; i++) {
            cur = cur.next;
        }
        ListNode start = cur.next;
        // 翻轉(zhuǎn)后start是翻轉(zhuǎn)部分的尾節(jié)點(diǎn)
        ListNode reverseHead = reverse(cur.next);
        cur.next.next = next;
        cur.next = reverseHead;
        return dummy.next;
    }
}