92.反转链表2

[chasingsnail]

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

递归

递归的思路是先构造反转 n 之前的链表方法，停止条件是 n === 1，此时已经找到了需要被反转的最后的一个节点，这时记录下该节点的后一个节点用来给原链表的 head.next。
有了上述方法后，同样利用递归创造当 m === 1 的条件，此时拿到链表中需要被反转的第一个节点，此时调用上述方法进行反转。其余部分正常通过 head.next = head.next 衔接

let nex = null

var reverseBetween = function(head, m, n) {
    // 反转从 m 至 n 的链表
    if (m === 1) {
        return reverseBeforeN(head, n)
    }
    head.next  = reverseBetween(head.next, m - 1, n - 1)
    return head
};

// 反转 n 之前的链表
var reverseBeforeN = function (head, n) {
    if (n === 1) {
        nex = head.next
        return head
    }
    
    const last = reverseBeforeN(head.next, n - 1)
    head.next.next = head
    head.next = nex
    return last
}

头插法

头插法的思路在于固定住需要反转的节点前一个节点 pre，创造两个指针 start 与 then，start 代表未反转的第一个节点，then 代表 start 之后的节点，主要思路是不断地向后移动 start，将 then 节点插入至 pre 之后，由此完成反转。

var reverseBetween = function(head, m, n) {
    let dummy = new ListNode(0)
    dummy.next = head

    let pre = dummy

    // 寻找需要反转链表的前一个节点，即头部 pre
    for (let i = 0; i < m - 1; i++) {
        pre = pre.next
    }

    let start = pre.next
    let then = start.next

    for (let i = 0; i < n - m; i++) {
        start.next = then.next
        // 将 then 的 next 指向固定 pre 的下一个节点，这样便实现了插入头部
        then.next = pre.next
        prev.next = then
        then = start.next
    }

    // 假设 m = 2，n = 4，list：[1, 2, 3, 4, 5]
    // [1, 2, 3, 4, 5] pre -> 1 start -> 2 then -> 3
    // first 1, 3, 2, 4, 5 pre -> 1 start -> 2 then -> 4
    // second  1, 4, 3, 2, 5 start -> 2 then -> 5 (end)

    return dummy.next
}