LeetCode LCR 021. 删除链表的倒数第 N 个结点

Categories:

题目描述
思路分析
1. 解法一：快慢指针（固定间距 N+1）（推荐）
相似题目

题目描述

✅ LCR 021. 删除链表的倒数第 N 个结点

思路分析

解法一：快慢指针（固定间距 N+1）（推荐）

核心思路：

让 fast 比 slow 多走 n+1 步，维持固定间距；当 fast 到达链表末尾（nil）时，slow 恰好停在倒数第 n 个节点的前驱，执行一次断链即可。

若 fast 多走 n 步，两者同步移动后 fast.Next == nil 时，slow 指向待删节点本身；但删除链表节点需要操作前驱（slow.Next = slow.Next.Next），所以需再多走 1 步。

创建虚拟头节点 dummy → head，slow、fast 均从 dummy 出发，fast 先走 n+1 步，再同步右移直到 fast == nil，最后执行 slow.Next = slow.Next.Next。

虚拟头节点的作用：当待删节点是原头节点时，slow 仍停在 dummy，无需特判。

举例：1 → 2 → 3 → 4 → 5，n=2，fast 先走 3 步指向节点 3，同步移动后 slow=4, fast=nil，删除节点 5，结果为 1 → 2 → 3 → 4。

复杂度分析：

时间复杂度：O(L)，其中 L 为链表长度，只对链表进行一次完整遍历。

空间复杂度：O(1)，只额外使用两个指针。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建哨兵结点，简化删除头结点的逻辑
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode fast = dummy;
        ListNode slow = dummy;

        // 快指针先走 n + 1 步
        // 走 n + 1 步是为了让 slow 最终停在待删除结点的前一个位置
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 快慢指针同时移动，直到快指针到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 此时 slow 指向待删除结点的前驱，执行删除
        slow.next = slow.next.next;

        // 返回真正的头结点
        return dummy.next;
    }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	slow, fast := dummy, dummy

	// 快指针先走 n+1 步，使 slow 最终停在待删节点的前驱
	for i := 0; i <= n; i++ {
		fast = fast.Next
	}

	// 快慢指针同步移动，直到快指针到达链表末尾
	for fast != nil {
		slow = slow.Next
		fast = fast.Next
	}

	// slow 停在待删节点的前驱，执行断链
	slow.Next = slow.Next.Next

	return dummy.Next
}

相似题目

题目	难度	考察点
876. 链表的中间结点	简单	快慢指针
141. 环形链表	简单	快慢指针
142. 环形链表 II	中等	快慢指针
234. 回文链表	简单	快慢指针、反转链表
160. 相交链表	简单	双指针
61. 旋转链表	中等	链表、双指针
82. 删除排序链表中的重复元素 II	中等	链表
203. 移除链表元素	简单	链表、虚拟头节点
1721. 交换链表中的节点	中等	链表、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/17103820