本题采用前后双指针算法又称“固定间距窗口法”或“快慢指针间距法”结合哑节点辅助设计解决单链表任意倒数指定位置节点的删除问题。其核心本质是通过先导指针提前步进建立一个长度为 n 的固定跨度窗口使双指针同速推进时后导指针能够精准停留在待删除节点的前驱位置从而将复杂的倒数定位转化为单遍线性扫描。当前提供的源码实现了在时间复杂度 O(N) 和额外空间复杂度 O(1) 条件下的全局最优原地修改最终走向是高效安全地移除目标节点并返回正确的链表头。一、 问题本质与数据模型对于由ListNode构成的单链表由于指针域next的单向不可逆性程序无法直接从尾部进行逆向追溯。若要删除倒数第 n 个节点其核心难点在于定位该节点的前驱节点即倒数第 n1 个节点。传统思路需要先完整遍历一遍链表以获取总长度 sz再通过二次遍历移动 sz - n 步找到目标位置。为了在一遍线性扫描中完成定位与删除算法引入了两个关键物理模型“哑节点Dummy Node边界模型”当要删除的节点恰好是头节点即 n 等于链表总长度 sz时头节点缺乏前驱节点传统的删除逻辑prev.next prev.next.next将因找不到prev而失效。通过在head之前挂载一个dummy节点能够强制使原头节点降级为普通内部节点从而将所有删除边界归一化。“固定间距滑窗模型”设置fast和slow两个指针。先让fast自dummy出发向前步进 n 步此时fast与slow之间形成了宽度为 n 的拓扑间距。当两个指针以相同速度同步向前推进直到fast到达链表末尾最后一个节点时两者的相对间距保持不变此时slow指针必然完美卡位在倒数第 n1 个节点上。二、 算法演进对比在解决删除链表倒数第 N 个节点的问题时双指针滑动窗口法在时空效率的综合表现上达到了最优解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷长度计数两遍扫描法O(N)O(1)第一遍累加计数获取总长度 sz第二遍线性步进到 sz - n 的位置执行删除需要对链表执行两次物理扫描无法满足“只遍历一遍”的高效控制流约束栈存储逆序弹出法O(N)O(N)遍历链表将所有节点压入栈中利用栈的先进后出特性连续弹出 n 个节点栈顶即为前驱产生额外的线性空间存储开销在长链表下内存损耗明显双指针间距法当前解法O(N)O(1)构建长度为 n 的控制窗口同步步进使后导指针直接锁定前驱节点依赖对快指针前向探针的精确控制代码编写需防控越界异常三、 核心分支控制逻辑与决策证明当前源码的控制流完全由一个前置for循环与一个while (fast.next ! null)同步控制网串联而成其决策分支证明如下1. 窗口间距建立for (int i 0; i n; i)执行fast fast.next;连续执行 n 次。数学证明初始时fast和slow均指向偏移起点dummy索引设为 0。执行 n 次步进后fast的相对坐标变为 n而slow保持在 0。结论两指针在空间上建立了绝对值等于 n 的节点位移差滑窗的物理边界初始化完成。2. 同步推进与触底判定while (fast.next ! null)执行fast与slow同时向后移动 1 位。数学证明设链表总长度为 sz不含dummy则最后一个节点的索引为 sz。当fast.next null时意味着fast指针已经精准停留在最后一个节点索引为 sz。由于两个指针全程同速推进相对位移差恒等于 n因此此时slow指针的坐标为sz - n。结论在以dummy为起点的索引体系中第sz - n个节点恰好是真实链表中待删除节点倒数第 n 个索引为sz - n 1的绝对前驱节点。3. 物理节点移除slow.next slow.next.next;执行跨越目标节点进行指针域重定向。结论由于slow已经停留在目标前驱上直接将其next指向“下下个”节点在拓扑结构上使倒数第 n 个节点与主链彻底断开依靠垃圾回收机制实现内存释放。四、 算法执行状态机步进示例以输入链表head [1, 2, 3, 4, 5]n 2为例期望删除倒数第 2 个节点即数字4指针状态机的演进过程如下表所示步骤slow 当前指向fast 当前指向fast.next 状态执行的核心逻辑与滑窗动作链表内部拓扑及间距说明初始dummy (0)dummy (0)1 (非空)挂载哑节点双指针在起点对齐窗口间距尚未建立间距 01dummy (0)2 (值)3 (非空)前置for循环结束fast移动 2 步成功建立宽度为 2 的间距窗口21 (值)3 (值)4 (非空)fast.next ! null双指针同步后移 1 步窗口向右滑动间距保持为 232 (值)4 (值)5 (非空)fast.next ! null双指针同步后移 1 步窗口向右滑动间距保持为 243 (值)5 (值)nullfast.next null条件不满足退出whilefast触底末梢slow精准卡位在前驱3上53 (值)5 (值)-执行slow.next slow.next.next节点4被跳过链表重组为1-2-3-5五、 源码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 创建哑节点 dummy强行统一头节点删除与其他节点删除的控制流边界 ListNode dummy new ListNode(0, head); // 初始化先导快指针 fast 指向哑节点 ListNode fast dummy; // 初始化后导慢指针 slow 指向哑节点 ListNode slow dummy; // 步骤 1让快指针先行推进 n 步在双指针间构建长度为 n 的空间滑窗 for (int i 0; i n; i) { fast fast.next; } // 步骤 2双指针同速保持推进当快指针的 next 触底 null 时停止 while (fast.next ! null) { fast fast.next; slow slow.next; } // 步骤 3此时 slow 正好处于待删除节点的前驱位置执行原地越过拼接 slow.next slow.next.next; // 返回剥离 dummy 哨兵后的真实链表新头节点 return dummy.next; } }六、 复杂度分析1. 时间复杂度O(N)分析设链表的总节点数为 N。算法的第一阶段中快指针fast独立向前行进 n 步第二阶段中fast指针从当前的第 n 个节点一直平滑步进至最后一个节点第 N 个节点移动了 N - n 步。两个阶段中快指针整体移动的步伐总和为n (N - n) N次。结论算法在全流程中对链表执行且仅执行了单次线性扫描总比较与位移操作次数与链表长度呈严格的正比关系。2. 空间复杂度O(1)分析算法在执行期间除了实例化了一个作为安全防护网的虚拟哑节点dummy之外仅在系统栈内存中分配了fast和slow两个基础类型的局部引用指针。所有修改均通过重定向已有节点的引用域原地In-place完成。结论没有申请任何与输入链表长度相关的外部临时存储矩阵内存空间资源消耗恒定为常数阶。