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

题目链接：19. 删除链表的倒数第 N 个结点

题目描述

给定一个单向链表的头节点 head，要求在仅进行一次完整遍历的前提下，删除该链表的倒数第 $n$ 个节点，并返回修改后的链表头节点。

核心思考

解决本题的核心在于单向链表的逆序节点定位。单向链表结构由于缺乏前驱指针，且动态数据结构无法以 $O(1)$ 的代价预知总长度，直接定位倒数第 $n$ 个节点通常需要执行两阶段遍历（一次遍历统计链表总规模，二次遍历正向逼近目标点）。为了满足一次扫描即解除引用的 $O(N)$ 最优解，需引入双指针（快慢指针）模型，利用步长差规避链表全长的先决计算。

1. 步长偏移量的构建

实例化快慢两个引用指针（p1 与 p2）。设链表总跨度为 $L$：

• 驱动快指针 p1 预先正向偏移 $k$ 个节点。
• 随后驱动 p1 与 p2 同步迭代。当快指针 p1 触发边界条件越界（即 p1 == None，行进总跨度为 $L$）时，受步长偏移制约，慢指针 p2 的行进跨度必然为 $L - k$。
• 此时 p2 所在的局部内存块正是链表的倒数第 $k$ 个节点。

2. 前驱节点定位与引用阻断

在常规的链表删除操作中，必须获取被删节点的前驱节点引用（即将前驱节点的 next 指向目标节点的下一节点）。

• 执行倒数第 $n$ 个节点的删除，核心上等同于定位链表的倒数第 $n+1$ 个节点。
• 因此，快指针预分配的步距约束需设为 $n+1$。当快指针越界时，慢指针精准停留至被删节点的前驱寻址点，以实现局部节点的解引用（Dereference）操作。

3. Edge Case：首部引用的边界风险

当目标删除节点严格为链表实际头节点（即链表容量 $L = n$ 的边界条件）时，头节点不具备合法前驱引用点。若缺乏防御机制，常规步距跨度会导致指针越界异常。

• 虚拟头节点（Dummy Node）方案：在链表起始边界前置构造一块静态内存 dummy（将虚拟节点的 next 指针挂接为 head），作为双指针的起始基址。
• 这一构造从逻辑架构上将全量元素内敛为常规操作，确保原头节点退化为拥有合法前置引用的非边界节点，完全规避了条件分支（If-Else）的特例判断。

解题思路 (Python)

以下代码涵盖基础的逆序节点查找模板（函数 findFromEnd），以及搭载虚拟头节点的单次遍历正规解答（类 Solution）。

# 定位链表的倒数第 k 个节点
def findFromEnd(head: ListNode, k: int) -> ListNode:
    p1 = head
    # 快指针 p1 预先跨越 k 步
    for i in range(k):
        p1 = p1.next
    p2 = head
    # 快慢指针同步游走，直至快指针越界触发 Null
    while p1 != None:
        p2 = p2.next
        p1 = p1.next
    # 越界触发时，慢指针 p2 指向倒数第 k 个节点
    return p2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        # 定位目标节点的前驱节点（即倒数第 n+1 个节点）
        p1 = p2 = dummy
        for i in range(n+1):
            p1 = p1.next
        while(p1 != None):
            p1 = p1.next
            p2 = p2.next
        
        # 此时 p2 驻留于倒数第 n+1 个节点，执行 next 引用阻断与重定向
        p2.next = p2.next.next
        return dummy.next

复杂度分析

• 时间复杂度：$O(L)$，其中 $L$ 为链表的节点总数。全局仅涉及快指针完整扫视过一次整个数据结构的遍历开销，时间复杂度保持严格线性。
• 空间复杂度：$O(1)$。算法内部额外操作仅开辟了常数级别的内存引用指针（p1、p2 及虚拟头节点 dummy），不存在随节点总量攀升的空间复杂度溢出情况。