一、题目描述19. 删除链表的倒数第 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]提示链表中结点的数目为sz1 sz 300 Node.val 1001 n sz进阶你能尝试使用一趟扫描实现吗二、解题思路概览删除倒数第 N 个结点核心是找到它的前驱节点。常见解法有三种解法时间复杂度空间复杂度特点两次遍历计算长度O(L)O(1)最简单容易理解快慢指针一次遍历O(L)O(1)面试首选满足进阶要求栈辅助O(L)O(L)利用栈的 LIFO 特性三、解法一两次遍历计算链表长度3.1 思路第一次遍历计算链表的总长度length倒数第n个结点就是正数第length - n个结点从 1 开始计数第二次遍历找到第length - n - 1个结点前驱将其next指向下下个结点注意如果删除的是头结点需要特殊处理。3.2 代码实现javaclass Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 1. 计算链表长度 int length 0; ListNode p head; while (p ! null) { length; p p.next; } // 2. 计算需要删除的节点是正数第几个从1开始 int targetIndex length - n 1; // 3. 处理删除头结点的情况 if (targetIndex 1) { return head.next; } // 4. 找到要删除节点的前驱 ListNode prev head; for (int i 1; i targetIndex - 1; i) { prev prev.next; } // 5. 删除节点 prev.next prev.next.next; return head; } }3.3 复杂度分析时间复杂度O(L)遍历两次链表。空间复杂度O(1)只用了几个指针变量。四、解法二快慢指针一次遍历⭐4.1 思路使用两个指针slow和fast初始化都指向哑结点dummy nodefast先移动n步然后slow和fast同时移动直到fast到达链表末尾此时slow.next就是要删除的节点因为slow和fast之间始终相隔n个节点删除slow.next即可。使用哑结点可以避免对头结点的特殊处理使代码更统一。4.2 代码实现javaclass Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); ListNode slow dummy; ListNode fast dummy; // 快指针先走 n 步 for (int i 0; i n; i) { fast fast.next; } // 同时移动直到 fast 到达末尾 while (fast.next ! null) { slow slow.next; fast fast.next; } // 删除 slow.next slow.next slow.next.next; return dummy.next; } }4.3 图解示例以head [1,2,3,4,5]n 2为例text初始: dummy → 1 → 2 → 3 → 4 → 5 → null slow, fast 都指向 dummy 第1步: fast 先走 n2 步 dummy → 1 → 2 → 3 → 4 → 5 → null ↑ ↑ slow fast 第2步: 同时移动直到 fast.next null dummy → 1 → 2 → 3 → 4 → 5 → null ↑ ↑ slow fast 此时 slow.next 指向节点 4正是要删除的节点 执行 slow.next slow.next.next 即可删除节点 44.4 复杂度分析时间复杂度O(L)只遍历一次链表。空间复杂度O(1)。五、解法三使用栈5.1 思路遍历链表将所有节点依次压入栈中从栈顶弹出n个节点即倒数第n个节点会留在栈顶再弹出一次得到倒数第n个节点的前一个节点修改指针完成删除。5.2 代码实现javaclass Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0, head); DequeListNode stack new ArrayDeque(); ListNode p dummy; // 将链表节点包括哑结点全部入栈 while (p ! null) { stack.push(p); p p.next; } // 弹出 n 个节点此时栈顶就是倒数第 n 个节点的前驱 for (int i 0; i n; i) { stack.pop(); } ListNode prev stack.peek(); // 前驱节点 prev.next prev.next.next; // 删除目标节点 return dummy.next; } }5.3 复杂度分析时间复杂度O(L)遍历一次 栈操作 O(1) 每次。空间复杂度O(L)栈需要存储所有节点。六、解法对比与总结方法时间复杂度空间复杂度是否一次遍历推荐度两次遍历O(L)O(1)❌⭐⭐⭐快慢指针O(L)O(1)✅⭐⭐⭐⭐⭐栈O(L)O(L)❌⭐⭐6.1 面试建议首选快慢指针法一次遍历 O(1) 空间完美满足进阶要求也是面试官最期待的答案。注意使用哑结点dummy node来简化头结点的删除逻辑。边界条件n有效1 ≤ n ≤ sz题目已保证无需额外校验。6.2 常见错误忘记处理头结点删除如果不使用哑结点需要单独判断targetIndex 1的情况。快慢指针初始位置错误fast先走n步如果初始都指向head则删除头结点时会出现空指针异常。使用哑结点可避免。快慢指针移动条件应该是fast.next ! null而不是fast ! null否则slow会多走一步。七、相关链接题目链接19. 删除链表的倒数第 N 个结点 - 力扣LeetCode官方题解删除链表的倒数第 N 个结点官方题解