【链表】反转链表

[miracles1919]

参考：递归反转链表的一部分

[miracles1919]

206. 反转链表

// 递归版本
var reverseList = function (head) {
    if (head === null || head.next === null) {
        return head
    }

    const last = reverseList(head.next)
    head.next.next = head
    head.next = null

    return last
};

// 循环版本
var reverseList = function (head) {
    let curr = head, prev = null

    while (curr) {
        let next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }

    return prev
};

[miracles1919]

92. 反转链表 II

先处理反转前n个节点

// 反转节点后面的节点
let next
var reverseN = function(head, n) {
    if (n === 1) {
        next = head.next
        return head
    }

    const last = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = next
    return last
}

反转 [left, right] 就简单了

var reverseBetween = function(head, left, right) {
    if(left === 1) return reverseN(head, right)
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head
};

---

循环版本

var reverseBetween = function (head, left, right) {
    const dummy = new ListNode()
    dummy.next = head
    let prev = dummy
    for(let i = 1; i < left; i++) {
        prev = prev.next
    }

    let curr = prev.next
    for(let i = 0; i < right -left; i++) {
        let next = curr.next
        curr.next = next.next
        next.next = prev.next
        prev.next = next
    }

    return dummy.next
};