删除链表的倒数第N个节点 (opens new window)

• 难度：Medium
• 标签：链表 快慢指针

刷题思路

• [x] 先计算长度，再删除节点（两轮遍历）
• [x] 双指针间隔n步推进（一轮遍历）

方法 1 先计算长度，再删除节点（两轮遍历）

• 复杂度：
  • 时间 O(N). 一轮遍历计算长度，一轮遍历删节点.
  • 空间 O(1). 原地操作.
• 结果:
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了70.03%的用户
  • 内存消耗：39.8 MB, 在所有 JavaScript 提交中击败了5.03%的用户

var removeNthFromEnd = function(head, n) {
    let [len, curr] = [0, head]
    while (curr) [len, curr] = [len+1, curr.next] // 计算长度
    const newHead = new ListNode(null)
    newHead.next = head
    let prev = newHead // prev最终将到达待删除节点的前一个节点
    let [target, count] = [len-n, 0] // 计算目标位置
    while (count < target) { // 推进直到到达目标位置
        [prev, count] = [prev.next, count+1]
    }
    prev.next = prev.next.next // 删除逻辑, 前节点的next指向"被删除节点"的下一个节点
    return newHead.next
};

方法 2 快慢指针间隔n步推进（一轮遍历）

• 复杂度：
  • 时间 O(N). 一轮遍历解决.
  • 空间 O(1). 原地操作.
• 结果:
  • 执行用时：76 ms, 在所有 JavaScript 提交中击败了88.35%的用户
  • 内存消耗：38.5 MB, 在所有 JavaScript 提交中击败了13.26%的用户

var removeNthFromEnd = function(head, n) {
    const newHead = new ListNode(null)
    newHead.next = head
    let [prev, curr] = [newHead, newHead] // prev 最终将到达待删除节点的前一个节点
    for (let i=0; i<n; i++) curr = curr.next // 推进 curr 直到比 prev 领先 n 个节点
    while (curr.next) { // curr.next 存在时，两个指针继续推进
        prev = prev.next
        curr = curr.next
    }
    prev.next = prev.next.next // curr.next 不存在时，prev.next 即倒数第 n 个节点, 删之
    return newHead.next
};

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