高效删除链表倒数节点最优实现
最新回答
蝶き梦
2026-08-17 10:36:39
高效删除链表倒数第n个节点的最优实现是使用快慢指针法，通过一趟扫描完成操作。
核心思路：利用快慢指针的差距定位目标节点。快指针先移动n步，随后快慢指针同步移动，当快指针到达链表末尾时，慢指针恰好指向待删除节点的前驱节点。
关键步骤：
引入哑节点：简化头节点删除的边界处理，避免单独判断头节点删除的情况。
初始化指针：快慢指针均指向哑节点，确保初始位置一致。
快指针先行：快指针先移动n步，建立与慢指针的n个节点间隔。
同步移动：快慢指针同时移动，直到快指针到达链表末尾（fast.next == null）。
删除节点：调整慢指针的next指向，跳过待删除节点。
返回结果：哑节点的next即为新链表的头节点。
代码实现（Java）：
class ListNode { int val; ListNode next; ListNode(int x) { val = x; }}public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy, slow = dummy; // 快指针先行n步 for (int i = 0; i < n; i++) { fast = fast.next; } // 同步移动至快指针到达末尾 while (fast.next != null) { fast = fast.next; slow = slow.next; } // 删除慢指针的下一节点 slow.next = slow.next.next; return dummy.next; }}复杂度分析：
时间复杂度：O(sz)，仅需一次遍历链表，sz为链表长度。
空间复杂度：O(1)，仅使用固定数量的指针变量。
边界处理：
删除头节点：哑节点确保慢指针始终指向待删除节点的前驱，无需特殊处理。
单节点链表：若链表仅含一个节点且需删除（n=1），直接返回null。
示例验证：
输入：[1,2,3,4,5]，n=2过程：快指针先移动2步至节点2，同步移动后慢指针停在节点3（倒数第2个节点的前驱），删除节点4。输出：[1,2,3,5]。
输入：[1]，n=1过程：快指针移动1步后直接到达末尾，慢指针指向哑节点，删除头节点。输出：[]。
优势总结：
单次扫描：避免两次遍历链表（如先计算长度再定位），提升效率。
代码简洁：通过哑节点统一处理所有边界情况，逻辑清晰。
鲁棒性：适用于任意合法输入（1 ≤ n ≤ sz），包括极端情况。
此方法通过精妙的指针操作，在O(sz)时间内完成删除，是解决该问题的最优方案。
热门标签
