# 0019. 删除链表的倒数第N个节点 ## 题目地址(19. 删除链表的倒数第N个节点) <https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 进阶： 你能尝试使用一趟扫描实现吗？ ``` ``` ## 前置知识 - 链表 - 双指针 ## 公司 - 阿里 - 百度 - 腾讯 - 字节 ## 思路 双指针，指针 A 先移动 n 次， 指针 B 再开始移动。当 A 到达 null 的时候， 指针 b 的位置正好是倒数 n 我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。 设置虚拟节点 dummyHead 指向 head 设定双指针 p 和 q，初始都指向虚拟节点 dummyHead 移动 q，直到 p 与 q 之间相隔的元素个数为 n 同时移动 p 与 q，直到 q 指向的为 NULL 将 p 的下一个节点指向下下个节点  (图片来自： <https://github.com/MisterBooo/LeetCodeAnimation>) ## 关键点解析 1. 链表这种数据结构的特点和使用 2. 使用双指针 3. 使用一个 dummyHead 简化操作 ## 代码 Support: JS, Java - Javascript Implementation ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {ListNode} head * @param {number} n * @return {ListNode} */</span> <span class="hljs-keyword">var</span> removeNthFromEnd = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">head, n</span>) </span>{ <span class="hljs-keyword">let</span> i = <span class="hljs-params">-1</span>; <span class="hljs-keyword">const</span> noop = { next: <span class="hljs-params">null</span>, }; <span class="hljs-keyword">const</span> dummyHead = <span class="hljs-keyword">new</span> ListNode(); <span class="hljs-title">// 增加一个dummyHead 简化操作</span> dummyHead.next = head; <span class="hljs-keyword">let</span> currentP1 = dummyHead; <span class="hljs-keyword">let</span> currentP2 = dummyHead; <span class="hljs-keyword">while</span> (currentP1) { <span class="hljs-keyword">if</span> (i === n) { currentP2 = currentP2.next; } <span class="hljs-keyword">if</span> (i !== n) { i++; } currentP1 = currentP1.next; } currentP2.next = ((currentP2 || noop).next || noop).next; <span class="hljs-keyword">return</span> dummyHead.next; }; ``` ``` - Java Code ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> ListNode <span class="hljs-title">removeNthFromEnd</span><span class="hljs-params">(ListNode head, <span class="hljs-keyword">int</span> n)</span> </span>{ TreeNode dummy = <span class="hljs-keyword">new</span> TreeNode(<span class="hljs-params">0</span>); dummy.next = head; TreeNode first = dummy; TreeNode second = dummy; <span class="hljs-keyword">if</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-params">0</span>; i<=n; i++) { first = first.next; } <span class="hljs-keyword">while</span> (first != <span class="hljs-keyword">null</span>) { first = first.next; second = second.next; } second.next = second.next.next; <span class="hljs-keyword">return</span> dummy.next; } } ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(1)O(1)O(1) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。