leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以本仓库的 19.removeNthNodeFromEndofList.md 题为骨架结合仓库内的 链表专题 与 双指针讲义深入剖析删除链表倒数第 N 个节点这一经典中等题的**双指针 虚拟头dummyHead**解法。读完你将掌握如何用一趟扫描完成删除、为什么虚拟头能让头结点免于特殊判断、以及固定间距指针这一双指针套路如何迁移到其他链表题目。题目回顾给定一个链表删除链表的倒数第 n 个节点并且返回链表的头结点。示例给定一个链表: 1-2-3-4-5, 和 n 2. 当删除了倒数第二个节点后链表变为 1-2-3-5.说明给定的 n 保证是有效的。进阶你能尝试使用一趟扫描实现吗这道题的核心难点在于单链表无法随机访问只能靠next指针顺序遍历因此倒数第 n 个节点无法直接定位。而进阶要求的一趟扫描正是引出双指针解法的关键。前置知识链表物理存储上非连续、非顺序依靠指针链接次序的线性结构。链表的插入、删除操作只需要修正前驱节点的next指针在给定前驱指针的情况下时间复杂度为 $O(1)$但其缺点是无法按下标随机访问。链表的基础操作插入、删除、遍历与复杂度分析可以参考仓库中的 链表专题。双指针一种算法思想用两个指针协同完成遍历。本题属于双指针中的固定间距指针两个指针间距相同、步长相同类型仓库 91 天学算法·双指针讲义 将其与快慢指针、左右端点指针并列并给出模板l 0 r k while 没有遍历完 自定义逻辑 l 1 r 1 return 合适的值本题正是固定间距指针最经典的应用场景之一一次遍历One Pass求链表的倒数第 k 个元素。思路分析双指针让两指针间距恒为 n直观的解法是两次遍历第一次统计链表长度len第二次找到第len - n个节点并删除。这需要两趟扫描无法满足进阶要求。改用双指针后只需一趟扫描设置两个指针 A记为p和 B记为q初始都指向虚拟头节点dummyHead。指针 A 先移动 n 次此时 A 与 B 之间恰好相隔 n 个节点。A、B 同步移动直到 A 到达null。此时 B 的位置正好是倒数第 n 个节点的前驱。将 B 的next指向下下个节点即完成删除。上述动画过程可用仓库 assets/19.removeNthNodeFromEndOfList.gif 直观感受该动图与本题主题强相关展示了双指针拉开 n 步间距后同步前进的全过程算法步骤dummyHead 简化头结点处理设置虚拟节点dummyHead指向head简化判断使得头结点不需要特殊判断。设定双指针p和q初始都指向虚拟节点dummyHead。移动q直到p与q之间相隔的元素个数为 n。同时移动p与q直到q指向 NULL。将p的下一个节点指向下下个节点。关于虚拟节点链表专题 中专门强调过它的两个作用将头节点变成中间节点简化判断。虚拟头指向原头节点后虚拟头成为新的头节点它不参与运算因此不需要为头节点可能被删除做特殊判断。本题中当n恰好等于链表长度时删除的是原头节点dummyHead的存在让这一边界情况与其他情况走完全相同的代码路径。通过在合适的时候断开链接返回链表的中间节点。本题最终返回dummyHead.next无论原头节点是否被删都能正确返回新链表的头。这也是 链表专题 总结的三个注意中边界问题的标准解法如果题目的头节点可能被移除那么考虑使用虚拟节点这样头节点就变成了中间节点就不需要为头节点做特殊判断了。关键点解析链表这种数据结构的特点和使用单链表只能单向遍历无法在 $O(1)$ 时间内拿到前驱节点这也是为什么删除操作需要维护一个前驱节点指针——链表的增删操作本质上都依赖前驱节点这是链表的特性天生决定的。使用双指针通过让两个指针保持固定间距 n一趟遍历即可定位到倒数第 n 个节点的前驱时间复杂度 $O(N)$、空间复杂度 $O(1)$满足一趟扫描的进阶要求。使用一个 dummyHead 简化操作虚拟头把头节点可能被删这一边界情况统一为普通中间节点的删除避免对head做特判分支。代码实现JS / Java / CPP原题解在 19.removeNthNodeFromEndofList.md 中给出了 JS、Java、CPP 三种实现下面结合仓库中 链表专题 提到的链表定义valnext逐一解读。Javascript Code/** * param {ListNode} head * param {number} n * return {ListNode} */ var removeNthFromEnd function (head, n) { let i -1; const noop { next: null, }; const dummyHead new ListNode(); // 增加一个dummyHead 简化操作 dummyHead.next head; let currentP1 dummyHead; let currentP2 dummyHead; while (currentP1) { if (i n) { currentP2 currentP2.next; } if (i ! n) { i; } currentP1 currentP1.next; } currentP2.next ((currentP2 || noop).next || noop).next; return dummyHead.next; };解读currentP1全程推进用计数器i控制currentP2的启动时机——当currentP1已经比currentP2多走了 n 步i n后currentP2才开始同步前进从而保证两者间距恒为 n。noop对象用于防御性取.next避免空指针异常。循环结束时currentP1指向null此时currentP2恰好停在待删除节点的前驱执行currentP2.next currentP2.next.next即完成删除。Java Code原文档 Java 版存在两处笔误使用了不存在的TreeNode类型、if写成了循环这里给出修正后的可运行版本/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode first dummy; ListNode second dummy; // first 先走 n 1 步保证 first 与 second 之间相隔 n 个节点 for (int i 0; i n; i) { first first.next; } while (first ! null) { first first.next; second second.next; } // second.next 即为待删除节点 second.next second.next.next; return dummy.next; } }注意这里first先走的是n 1步而非 n 步因为first停在null时second需要落在待删除节点的前驱上两者间距为 n 个节点因此先走n 1步多出的 1 步跨越dummy与head。CPP Codeclass Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *p head, *q head; while (n--) q q-next; if (!q) { head head-next; delete p; return head; } while (q-next) p p-next, q q-next; q p-next; p-next q-next; delete q; return head; } };CPP 版采用无虚拟头的写法q先走 n 步若q为空说明要删除的正是头节点直接移动head否则p、q同步走到q-next nullptr此时p指向待删除节点的前驱。与 JS/Java 版相比它需要显式处理删除头节点的分支且用delete释放被删节点内存体现了虚拟头写法在代码统一性上的优势代价是需要额外分配一个节点。复杂度分析时间复杂度$O(N)$其中 N 为链表长度。两个指针合计遍历链表一次。空间复杂度$O(1)$只使用了常数个额外指针变量虚拟头节点不计入额外数据规模。边界情况与易错点n 链表长度删除头节点使用dummyHead后无需特判统一走p 的下一个节点指向下下个节点即可CPP 无虚拟头版本则需要if (!q)分支。n 1删除尾节点p最终停在倒数第二个节点p.next p.next.next中p.next.next恰好为null删除后链表正确终止。链表只有一个节点dummyHead存在时p即dummyHead删除后返回null逻辑依然正确。从 链表专题 的经验看链表题目 90% 的错误集中在环、边界、前后序三类本题的易错点主要在边界头节点删除与指针顺序。该专题还给出了先穿再排后判空的实操口诀先确定修改next指针的代码再考虑语句顺序最后检查哪些解引用可能为null如second.next.next在second.next为null时会空指针需要依据n 有效的题目约束保证安全性。关联专题与延伸练习本题同时是仓库 链表专题虚拟头、边界处理、双指针定位倒数第 k 个元素与 91 天学算法·双指针讲义固定间距指针一次遍历求链表倒数第 k 个元素的直接落地案例。想要巩固虚拟头和双指针这两大套路可以继续阅读仓库中同样使用了这些技巧的题解21. 合并两个有序链表双链表拼接25. K 个一组翻转链表虚拟头 穿针引线61. 旋转链表双指针定位断点80. 删除排序数组中的重复项 II双指针读写定位86. 分隔链表双虚拟头拆分拼接92. 反转链表 II虚拟头 部分反转142. 环形链表 II快慢指针找环入口206. 反转链表指针修改的经典题总结删除链表倒数第 N 个节点是一道会了就不容易忘的经典题固定间距的双指针解决单链表无法随机访问倒数第 k 个元素的难题虚拟头节点消除头节点删除的边界分支两者结合便得到一趟扫描、$O(1)$ 空间的优雅解法。正如 链表专题 所言链表的考点无非指针的修改与链表的拼接做链表的题无它唯画图尔——先画出双指针拉开 n 步间距的示意图再对照图写代码就能稳定、无 bug 地 AC 本题及其延伸变形。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
leetcode 题解：19. 删除链表的倒数第 N 个节点 —— 双指针 + 虚拟头一次遍历详解
leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以本仓库的 19.removeNthNodeFromEndofList.md 题为骨架结合仓库内的 链表专题 与 双指针讲义深入剖析删除链表倒数第 N 个节点这一经典中等题的**双指针 虚拟头dummyHead**解法。读完你将掌握如何用一趟扫描完成删除、为什么虚拟头能让头结点免于特殊判断、以及固定间距指针这一双指针套路如何迁移到其他链表题目。题目回顾给定一个链表删除链表的倒数第 n 个节点并且返回链表的头结点。示例给定一个链表: 1-2-3-4-5, 和 n 2. 当删除了倒数第二个节点后链表变为 1-2-3-5.说明给定的 n 保证是有效的。进阶你能尝试使用一趟扫描实现吗这道题的核心难点在于单链表无法随机访问只能靠next指针顺序遍历因此倒数第 n 个节点无法直接定位。而进阶要求的一趟扫描正是引出双指针解法的关键。前置知识链表物理存储上非连续、非顺序依靠指针链接次序的线性结构。链表的插入、删除操作只需要修正前驱节点的next指针在给定前驱指针的情况下时间复杂度为 $O(1)$但其缺点是无法按下标随机访问。链表的基础操作插入、删除、遍历与复杂度分析可以参考仓库中的 链表专题。双指针一种算法思想用两个指针协同完成遍历。本题属于双指针中的固定间距指针两个指针间距相同、步长相同类型仓库 91 天学算法·双指针讲义 将其与快慢指针、左右端点指针并列并给出模板l 0 r k while 没有遍历完 自定义逻辑 l 1 r 1 return 合适的值本题正是固定间距指针最经典的应用场景之一一次遍历One Pass求链表的倒数第 k 个元素。思路分析双指针让两指针间距恒为 n直观的解法是两次遍历第一次统计链表长度len第二次找到第len - n个节点并删除。这需要两趟扫描无法满足进阶要求。改用双指针后只需一趟扫描设置两个指针 A记为p和 B记为q初始都指向虚拟头节点dummyHead。指针 A 先移动 n 次此时 A 与 B 之间恰好相隔 n 个节点。A、B 同步移动直到 A 到达null。此时 B 的位置正好是倒数第 n 个节点的前驱。将 B 的next指向下下个节点即完成删除。上述动画过程可用仓库 assets/19.removeNthNodeFromEndOfList.gif 直观感受该动图与本题主题强相关展示了双指针拉开 n 步间距后同步前进的全过程算法步骤dummyHead 简化头结点处理设置虚拟节点dummyHead指向head简化判断使得头结点不需要特殊判断。设定双指针p和q初始都指向虚拟节点dummyHead。移动q直到p与q之间相隔的元素个数为 n。同时移动p与q直到q指向 NULL。将p的下一个节点指向下下个节点。关于虚拟节点链表专题 中专门强调过它的两个作用将头节点变成中间节点简化判断。虚拟头指向原头节点后虚拟头成为新的头节点它不参与运算因此不需要为头节点可能被删除做特殊判断。本题中当n恰好等于链表长度时删除的是原头节点dummyHead的存在让这一边界情况与其他情况走完全相同的代码路径。通过在合适的时候断开链接返回链表的中间节点。本题最终返回dummyHead.next无论原头节点是否被删都能正确返回新链表的头。这也是 链表专题 总结的三个注意中边界问题的标准解法如果题目的头节点可能被移除那么考虑使用虚拟节点这样头节点就变成了中间节点就不需要为头节点做特殊判断了。关键点解析链表这种数据结构的特点和使用单链表只能单向遍历无法在 $O(1)$ 时间内拿到前驱节点这也是为什么删除操作需要维护一个前驱节点指针——链表的增删操作本质上都依赖前驱节点这是链表的特性天生决定的。使用双指针通过让两个指针保持固定间距 n一趟遍历即可定位到倒数第 n 个节点的前驱时间复杂度 $O(N)$、空间复杂度 $O(1)$满足一趟扫描的进阶要求。使用一个 dummyHead 简化操作虚拟头把头节点可能被删这一边界情况统一为普通中间节点的删除避免对head做特判分支。代码实现JS / Java / CPP原题解在 19.removeNthNodeFromEndofList.md 中给出了 JS、Java、CPP 三种实现下面结合仓库中 链表专题 提到的链表定义valnext逐一解读。Javascript Code/** * param {ListNode} head * param {number} n * return {ListNode} */ var removeNthFromEnd function (head, n) { let i -1; const noop { next: null, }; const dummyHead new ListNode(); // 增加一个dummyHead 简化操作 dummyHead.next head; let currentP1 dummyHead; let currentP2 dummyHead; while (currentP1) { if (i n) { currentP2 currentP2.next; } if (i ! n) { i; } currentP1 currentP1.next; } currentP2.next ((currentP2 || noop).next || noop).next; return dummyHead.next; };解读currentP1全程推进用计数器i控制currentP2的启动时机——当currentP1已经比currentP2多走了 n 步i n后currentP2才开始同步前进从而保证两者间距恒为 n。noop对象用于防御性取.next避免空指针异常。循环结束时currentP1指向null此时currentP2恰好停在待删除节点的前驱执行currentP2.next currentP2.next.next即完成删除。Java Code原文档 Java 版存在两处笔误使用了不存在的TreeNode类型、if写成了循环这里给出修正后的可运行版本/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode first dummy; ListNode second dummy; // first 先走 n 1 步保证 first 与 second 之间相隔 n 个节点 for (int i 0; i n; i) { first first.next; } while (first ! null) { first first.next; second second.next; } // second.next 即为待删除节点 second.next second.next.next; return dummy.next; } }注意这里first先走的是n 1步而非 n 步因为first停在null时second需要落在待删除节点的前驱上两者间距为 n 个节点因此先走n 1步多出的 1 步跨越dummy与head。CPP Codeclass Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *p head, *q head; while (n--) q q-next; if (!q) { head head-next; delete p; return head; } while (q-next) p p-next, q q-next; q p-next; p-next q-next; delete q; return head; } };CPP 版采用无虚拟头的写法q先走 n 步若q为空说明要删除的正是头节点直接移动head否则p、q同步走到q-next nullptr此时p指向待删除节点的前驱。与 JS/Java 版相比它需要显式处理删除头节点的分支且用delete释放被删节点内存体现了虚拟头写法在代码统一性上的优势代价是需要额外分配一个节点。复杂度分析时间复杂度$O(N)$其中 N 为链表长度。两个指针合计遍历链表一次。空间复杂度$O(1)$只使用了常数个额外指针变量虚拟头节点不计入额外数据规模。边界情况与易错点n 链表长度删除头节点使用dummyHead后无需特判统一走p 的下一个节点指向下下个节点即可CPP 无虚拟头版本则需要if (!q)分支。n 1删除尾节点p最终停在倒数第二个节点p.next p.next.next中p.next.next恰好为null删除后链表正确终止。链表只有一个节点dummyHead存在时p即dummyHead删除后返回null逻辑依然正确。从 链表专题 的经验看链表题目 90% 的错误集中在环、边界、前后序三类本题的易错点主要在边界头节点删除与指针顺序。该专题还给出了先穿再排后判空的实操口诀先确定修改next指针的代码再考虑语句顺序最后检查哪些解引用可能为null如second.next.next在second.next为null时会空指针需要依据n 有效的题目约束保证安全性。关联专题与延伸练习本题同时是仓库 链表专题虚拟头、边界处理、双指针定位倒数第 k 个元素与 91 天学算法·双指针讲义固定间距指针一次遍历求链表倒数第 k 个元素的直接落地案例。想要巩固虚拟头和双指针这两大套路可以继续阅读仓库中同样使用了这些技巧的题解21. 合并两个有序链表双链表拼接25. K 个一组翻转链表虚拟头 穿针引线61. 旋转链表双指针定位断点80. 删除排序数组中的重复项 II双指针读写定位86. 分隔链表双虚拟头拆分拼接92. 反转链表 II虚拟头 部分反转142. 环形链表 II快慢指针找环入口206. 反转链表指针修改的经典题总结删除链表倒数第 N 个节点是一道会了就不容易忘的经典题固定间距的双指针解决单链表无法随机访问倒数第 k 个元素的难题虚拟头节点消除头节点删除的边界分支两者结合便得到一趟扫描、$O(1)$ 空间的优雅解法。正如 链表专题 所言链表的考点无非指针的修改与链表的拼接做链表的题无它唯画图尔——先画出双指针拉开 n 步间距的示意图再对照图写代码就能稳定、无 bug 地 AC 本题及其延伸变形。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考