本文概览：本文以LeetCode经典题目"删除链表的倒数第 N 个结点"为例，从链表单向遍历的限制入手，分析为什么倒数删除不能像正序删除一样直接计数，再引出前后双指针保持固定距离的解法

一、题目

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

二、题目分析

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

目标：找到倒数第 n 个节点并删除它

核心难点：链表是单向的，只能从前往后遍历，不能从尾节点往前数

思路概览

Java实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 初始化
    ListNode front = head;
    ListNode behind = head;
    // 后指针先走n-1步
    for (int i = 0; i < n - 1; i++) {
        behind = behind.next;
    }
    // 记录前指针的前一个节点
    ListNode prev = null;
    // 前后指针同时走，直到后指针到达链表末尾
    while (behind.next != null) {
        prev = front;
        behind = behind.next;
        front = front.next;
    }
    // 让prev指向front的下一个节点
    if (prev != null) {
        prev.next = front.next;
    }
    // 如果prev为null，说明要删除的是头节点
    else {
        head = head.next;
    }
    return head;
}

思路简要说明

  1. 前后双指针：用 front 指向可能被删除的节点，用 behind 指向更靠后的节点

  2. 保持固定距离：先让 behind 走 n-1 步，使 behind 和 front 之间保持 n-1 个节点距离

  3. 同步移动：两个指针一起向前走，当 behind 到达最后一个节点时，front 正好指向倒数第 n 个节点

  4. 删除节点：用 prev 记录 front 的前一个节点，最后让 prev.next = front.next

三、思路详解

为什么倒数删除更麻烦？

如果题目是删除正数第 n 个节点，那很简单：从头节点开始向前走，用一个计数器数到第 n 个节点即可

但是现在要删除的是倒数第 n 个节点。倒数意味着它的位置是从链表尾部往前数出来的，而链表是单向的，我们无法从尾节点反向走回来

比如链表：

1
1 → 2 → 3 → 4 → 5

删除倒数第 2 个节点，也就是删除 4。站在尾节点 5 的视角看，往前走 1 步就是 4。但问题是：链表没有 prev 指针，尾节点 5 无法往前走到 4

所以这道题的核心矛盾就是：目标节点由尾部决定，但链表只能从头部向后遍历

暴力解法入手

最直观的想法有两种：

方法一：先计算链表长度

先遍历一遍链表，得到链表长度 len。倒数第 n 个节点，其实就是正数第 len - n + 1 个节点。然后再遍历一遍链表，找到这个节点并删除

  • 时间复杂度：O(n)，但是需要两次遍历
  • 空间复杂度：O(1)
  • 问题：虽然复杂度是 O(n)，但需要先知道长度，整体过程不够直接

方法二：反转链表再删除

既然倒数不好找，那可以把链表反转。反转后，原来的倒数第 n 个节点就变成了正数第 n 个节点，再删除就容易了

但这个思路也有明显问题：

  • 需要先反转链表
  • 删除后如果要保持原链表方向，还要再反转回来
  • 操作链表指针更多，容易写复杂

所以我们需要一个更自然的方法：能不能不反转链表，也不先计算完整长度，而是在一次遍历中找到倒数第 n 个节点？

双指针解法

核心思路

倒数第 n 个节点，本质上和尾节点之间有一个固定距离

如果要删除倒数第 n 个节点，那么它距离尾节点是 n-1 步：

1
2
3
4
5
6
1 → 2 → 3 → 4 → 5
            ↑   ↑
          front behind

删除倒数第2个节点时：front指向4，behind指向5
front和behind之间距离 = n-1 = 1

既然目标节点和尾节点之间有固定距离，那我们可以让两个指针从头开始，提前制造出这个距离

具体做法：

  1. front 和 behind 都从头节点出发
  2. 先让 behind 走 n-1 步
  3. 然后 front 和 behind 一起走
  4. 当 behind 到达链表最后一个节点时，front 正好指向倒数第 n 个节点

为什么是让 behind 先走 n-1 步？

因为倒数第 n 个节点到最后一个节点之间正好隔着 n-1 条边

例如删除倒数第 3 个节点：

1
2
3
4
5
6
7
1 → 2 → 3 → 4 → 5
        ↑       ↑
      front   behind

front = 3，behind = 5
3到5之间走两步：3→4→5
n = 3，所以距离 = n-1 = 2

所以只要让两个指针始终保持 n-1 的距离，当后指针到达最后一个节点时，前指针自然就是倒数第 n 个节点

为什么需要 prev？

单链表删除一个节点，必须拿到它的前一个节点，因为删除操作本质是：

1
prev.next = front.next;

如果只知道要删除的节点 front，但不知道它前面的节点，就无法让前一个节点跳过它

所以在两个指针同步移动时，用 prev 记录 front 的前一个节点：

1
2
prev = front;
front = front.next;

这样最后 front 指向要删除的节点，prev 就指向它的前一个节点

特殊情况：删除头节点

如果要删除的是头节点，例如：

1
2
1 → 2 → 3
删除倒数第3个节点，也就是删除1

此时 front 一开始就是 head，最终也会指向 head，而 prev 仍然是 null，因为 head 前面没有节点

所以代码中需要单独判断：

1
2
3
4
5
if (prev != null) {
    prev.next = front.next;
} else {
    head = head.next;
}

如果 prev == null，说明删除的是头节点，直接让 head = head.next 即可

举例说明

以 head = 1 → 2 → 3 → 4 → 5，n = 2 为例

第一步：behind 先走 n-1 = 1 步

1
2
3
1 → 2 → 3 → 4 → 5
↑   ↑
front behind

第二步：front 和 behind 同步移动

步骤 front behind prev
初始 1 2 null
1 2 3 1
2 3 4 2
3 4 5 3

此时 behind.next == null，说明 behind 到达最后一个节点，front 指向 4，也就是倒数第 2 个节点，prev 指向 3

第三步：删除 front

1
2
3
4
5
6
7
8
9
删除前：1 → 2 → 3 → 4 → 5
                  ↑
                front
              ↑
            prev

执行：prev.next = front.next

删除后：1 → 2 → 3 → 5

最终返回 1 → 2 → 3 → 5

  • 时间复杂度：O(n)，链表只遍历一次
  • 空间复杂度：O(1)，只使用几个指针变量