反转链表II (opens new window)

• 难度：Medium
• 标签：链表反转 递归

刷题思路

• [x] 迭代法
• [x] 递归法

方法 1 迭代法

• 思路: 区分前驱指针、反转部分、后续链表三个部分
• 复杂度：
  • 时间 O(N). 一次遍历.
  • 空间 O(1)
• 结果:
  • 执行用时：72 ms, 在所有 JavaScript 提交中击败了83.57%的用户
  • 内存消耗：37.5 MB, 在所有 JavaScript 提交中击败了5.03%的用户

var reverseBetween = function(head, m, n) {
    if (m === n) return head // 相等等于不反转
    const newHead = new ListNode(null)
    newHead.next = head
    // 前驱指针prev用于最后尾接"反转部分", 当前指针curr用于执行链表反转
    let [prev, curr] = [newHead, newHead.next]
    for (let i=1; i<m; i++) {
        prev = prev.next
        curr = curr.next
    }
    let res = null // 存储"反转部分"结果
    let currTail = curr // 存储初始 curr，反转后将成为"反转部分"的尾节点
    for (let i=m; i<=n; i++) {
        const next = curr.next
        curr.next = res
        res = curr
        curr = next
    }
    currTail.next = curr // "反转部分"尾接"后续链表"
    prev.next = res // 前驱指针尾接"反转部分"
    return newHead.next
};

方法 2 递归法

• 复杂度：
  • 时间 O(N). 共计一次遍历.
  • 空间 O(N). 递归调用栈的消耗.
• 结果:
  • 执行用时：80 ms, 在所有 JavaScript 提交中击败了60.11%的用户
  • 内存消耗：37.5 MB, 在所有 JavaScript 提交中击败了5.03%的用户

var reverseBetween = function(head, m, n) {
    if (!head || !head.next) return head
    if (m === 1) return reverseN(head, n)
    head.next = reverseBetween(head.next, m-1, n-1)
    return head
};

// 反转前N个节点
function reverseN (head, n) {
    if (n === 1) return head
    const res = reverseN(head.next, n-1)
    const next = head.next.next
    head.next.next = head
    head.next = next
    return res
}

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~