# 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。