删除链表的倒数第 N 个结点 - Stellar Observer Protocol

605 字

3 分钟

删除链表的倒数第 N 个结点

2025-08-23

Algorithms

链表

/

双指针

题目描述#

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路#

双指针技巧：
- 快指针先移动 N 步
- 慢指针从头开始同步移动
虚拟头节点：
- 创建哑节点简化头节点删除操作
- 始终返回 dummy.next 作为结果
同步移动：
- 快慢指针同步移动直至快指针到链表尾
- 此时慢指针指向待删除节点的前驱
删除操作：
- 修改慢指针的 next 指向下下节点
- 跳过需删除节点完成移除

关键洞察#

倒数位置转换：
- 倒数第 N 个 ≡ 正数第 (L-N+1) 个
- 双指针避免显式计算链表长度 L
间距控制原理：
- 快指针领先 N 步形成固定间距
- 当快指针到尾部时，慢指针恰在目标前驱
边界处理：
- 虚拟头节点统一处理头节点删除
- 处理 N>L 的情况（快指针提前到 null）
一次遍历：
- 仅需单次遍历即可完成删除
- 时间复杂度严格 O(L)

复杂度分析#

指标	说明
时间复杂度	O(L)：L 为链表长度，只需一次遍历
空间复杂度	O(1)：仅使用常数空间存储指针
最佳情况	O(1)：当删除头节点时

代码实现#

1
/**
2
 * Definition for singly-linked list.
3
 * function ListNode(val, next) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.next = (next===undefined ? null : next)
6
 * }
7
 */
8
/**
9
 * @param {ListNode} head
10
 * @param {number} n
11
 * @return {ListNode}
12
 */
13
var removeNthFromEnd = function (head, n) {
14
    const dummy = new ListNode(0, head); // 创建虚拟头节点，指向head
15
    let fast = dummy, slow = dummy;
16

17
    // 快指针先走 n+1 步
18
    for (let i = 0; i <= n; i++) {
19
        fast = fast.next;
20
    }
21

22
    // 快慢指针同时移动，直到快指针到达链表末尾
23
    while (fast) {
24
        fast = fast.next;
25
        slow = slow.next;
26
    }
27

28
    // 删除倒数第n个节点
29
    slow.next = slow.next.next;
30

31
    return dummy.next; // 返回真正的头节点
32
};