<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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://img.kancloud.cn/06/fd/06fd9a4a0dd680f8ad7319abc26c46a4_959x539.gif) (圖片來自: <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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看