【LeetCode热题100道笔记】删除链表的倒数第 N 个结点

题目描述

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

思考

通过快慢指针+前驱指针实现高效定位：先让快指针超前慢指针n步，再让两者同步遍历，当快指针抵达链表尾部（null）时，慢指针恰好指向要删除的“倒数第n个节点”，而前驱指针始终跟随慢指针，记录其前一个节点，最终通过前驱指针跳过目标节点完成删除；若快指针走n步后直接到尾，则说明要删除的是头节点，直接返回头节点的后继即可。

算法过程

1. 初始化指针：定义slow（慢指针）、fast（快指针），初始均指向链表头节点head；定义pre（前驱指针），初始也指向head（用于记录slow的前一个节点）。
2. 快指针超前n步：循环n次，每次将fast向后移动1步（拉开与slow的n步距离）。
3. 处理“删除头节点”场景：若fast移动n步后变为null（说明倒数第n个节点就是头节点），直接返回slow.next（跳过原头节点）。
4. 同步遍历找目标节点：循环移动fast、slow、pre，直到fast变为null：
   • 先将pre更新为当前slow（记录slow的前驱）；
   • 再将slow和fast分别向后移动1步；
   • 最终slow会指向要删除的“倒数第n个节点”，pre指向其前一个节点。
5. 删除目标节点：通过pre.next = pre.next.next，让前驱节点跳过slow（目标节点），完成删除。
6. 返回结果：返回原链表头节点head（此时已移除目标节点）。

该算法仅遍历链表1次，时间复杂度O(L)（L为链表长度），空间复杂度O(1)（仅用3个指针）。

代码

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @param {number} n* @return {ListNode}*/
var removeNthFromEnd = function(head, n) {let slow = head, fast = head;for(let i = 0; i < n; i++) {fast = fast.next;}if (!fast) {return slow.next;}let pre = slow;while (fast) {pre = slow;slow = slow.next;fast = fast.next;}if (!pre.next) {return null;}pre.next = pre.next.next;return head;
};