日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
LeetCode題解之刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)

前言

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、科爾沁網(wǎng)絡(luò)推廣、微信小程序、科爾沁網(wǎng)絡(luò)營(yíng)銷、科爾沁企業(yè)策劃、科爾沁品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供科爾沁建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18982081108，官方網(wǎng)址：www.cdcxhl.com

今天繼續(xù)說(shuō)鏈表常見(jiàn)問(wèn)題中的——?jiǎng)h除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)：

  • 單鏈表反轉(zhuǎn)
  • 兩個(gè)有序的鏈表合并
  • 刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)
  • 求鏈表的中間結(jié)點(diǎn)
  • 鏈表中環(huán)的檢測(cè)

題目：刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

進(jìn)階：你能嘗試使用一趟掃描實(shí)現(xià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]

解法一

首先容易想到的辦法就是想數(shù)組一樣，遍歷鏈表找到那個(gè)要被刪除的結(jié)點(diǎn)，所以先解決兩個(gè)問(wèn)題：

1、獲取鏈表的總長(zhǎng)度

 
 
 
 
    
  
  
  
  
  1. public int getLength(ListNode head){ 
    2. 
  
  
  
  
  2.         int n=0; 
    3. 
  
  
  
  
  3.         while(head!=null){ 
    4. 
  
  
  
  
  4.             n++; 
    5. 
  
  
  
  
  5.             head=head.next; 
    6. 
  
  
  
  
  6.         } 
    7. 
  
  
  
  
  7.         return n; 
    8. 
  
  
  
  
  8.     } 
    9.

2、找到結(jié)點(diǎn)之后，怎么刪除。

其實(shí)就是把next指向跨過(guò)去要?jiǎng)h除的結(jié)點(diǎn)就行了。

 
 
 
 
    
  
  
  
  
  1. tempNode.next=tempNode.next.next; 
    2.

但是，上述這個(gè)方法是刪除的tempNode.next結(jié)點(diǎn)，如果我們要?jiǎng)h除tempNode本身這個(gè)結(jié)點(diǎn)，那么就要把一開(kāi)始的結(jié)點(diǎn)提前到第一個(gè)結(jié)點(diǎn)之前。

比如我們要?jiǎng)h除鏈表的第一個(gè)結(jié)點(diǎn)，如果你本身的指針就指向第一個(gè)結(jié)點(diǎn)，那么通過(guò)上面這個(gè)刪除方法就永遠(yuǎn)刪除不了第一個(gè)結(jié)點(diǎn)了。

所以要把指針提前到第一個(gè)結(jié)點(diǎn)之前。

所以，綜上所述，我們得出以下解法：

 
 
 
 
    
  
  
  
  
  1. /** 
    2. 
  
  
  
  
  2.  * Definition for singly-linked list. 
    3. 
  
  
  
  
  3.  * public class ListNode { 
    4. 
  
  
  
  
  4.  *     int val; 
    5. 
  
  
  
  
  5.  *     ListNode next; 
    6. 
  
  
  
  
  6.  *     ListNode() {} 
    7. 
  
  
  
  
  7.  *     ListNode(int val) { this.val = val; } 
    8. 
  
  
  
  
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } 
    9. 
  
  
  
  
  9.  * } 
    10. 
  
  
  
  
  10.  */ 
    11. 
  
  
  
  
  11. class Solution { 
    12. 
  
  
  
  
  12.     public ListNode removeNthFromEnd(ListNode head, int n) { 
    13. 
  
  
  
  
  13.         int length=getLength(head); 
    14. 
  
  
  
  
  14.         //新建一個(gè)新的鏈表結(jié)點(diǎn)指向head頭結(jié)點(diǎn)，也就是上面要注意的特殊情況 
    15. 
  
  
  
  
  15.         ListNode lastNode=new ListNode(0,head); 
    16. 
  
  
  
  
  16.         ListNode tempNode=lastNode; 
    17. 
  
  
  
  
  17.         for(int i=0;i
  
  
  
  
  18.             tempNode=tempNode.next; 
    19. 
  
  
  
  
  19.         } 
    20. 
  
  
  
  
  20.         tempNode.next=tempNode.next.next; 
    21. 
  
  
  
  
  21.         return lastNode.next; 
    22. 
  
  
  
  
  22.     } 
    23. 
  
  
  
  
  23.  
    24. 
  
  
  
  
  24.     public int getLength(ListNode head){ 
    25. 
  
  
  
  
  25.         int n=0; 
    26. 
  
  
  
  
  26.         while(head!=null){ 
    27. 
  
  
  
  
  27.             n++; 
    28. 
  
  
  
  
  28.             head=head.next; 
    29. 
  
  
  
  
  29.         } 
    30. 
  
  
  
  
  30.         return n; 
    31. 
  
  
  
  
  31.     } 
    32. 
  
  
  
  
  32. } 
    33.

時(shí)間復(fù)雜度

用到了遍歷、時(shí)間復(fù)雜度為O(n)

空間復(fù)雜度

只用到幾個(gè)單獨(dú)的鏈表結(jié)點(diǎn)，所以空間復(fù)雜度為O(1)

解法二

再想想，可不可以不計(jì)算鏈表長(zhǎng)度呢?也就是題目上所說(shuō)的進(jìn)階解法，用一次掃描。

再鏈表中，有一種常用的方法，叫做快慢指針，意思就是用到兩個(gè)速度不同的指針解決一些問(wèn)題。

比如這個(gè)題中，我們使用一個(gè)快指針一個(gè)慢指針，并且讓快指針快n個(gè)結(jié)點(diǎn)，然后兩個(gè)指針一直往后移動(dòng)。當(dāng)快指針移動(dòng)到結(jié)尾，那么慢指針的位置就是我們要?jiǎng)h除的結(jié)點(diǎn)了。

當(dāng)然，這里也要考慮到當(dāng)前結(jié)點(diǎn)被刪除的情況，所以要把開(kāi)始結(jié)點(diǎn)提前到鏈表之前。

 
 
 
 
    
  
  
  
  
  1. public ListNode removeNthFromEnd(ListNode head, int n) { 
    2. 
  
  
  
  
  2.  //提前鏈表 
    3. 
  
  
  
  
  3.         ListNode LastNode=new ListNode(0,head); 
    4. 
  
  
  
  
  4.         ListNode FirstNode=LastNode; 
    5. 
  
  
  
  
  5.         ListNode SecondNode=head; 
    6. 
  
  
  
  
  6.         for(int i=0;i
  
  
  
  
  7.             SecondNode=SecondNode.next; 
    8. 
  
  
  
  
  8.         } 
    9. 
  
  
  
  
  9.  
    10. 
  
  
  
  
  10.         while(SecondNode!=null){ 
    11. 
  
  
  
  
  11.             FirstNode=FirstNode.next; 
    12. 
  
  
  
  
  12.             SecondNode=SecondNode.next; 
    13. 
  
  
  
  
  13.         } 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15.         FirstNode.next=FirstNode.next.next; 
    16. 
  
  
  
  
  16.          
    17. 
  
  
  
  
  17.         return LastNode.next; 
    18. 
  
  
  
  
  18.     } 
    19.

時(shí)間復(fù)雜度

時(shí)間復(fù)雜的為O(n)

空間復(fù)雜度

空間復(fù)雜度為O(1)

其他解法

還有其他的解法，比如用到棧先進(jìn)后出的原則，先把所有鏈表數(shù)據(jù)入棧，然后出棧n個(gè)數(shù)。剩下的棧頂就是要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)了，然后調(diào)用上述的刪除結(jié)點(diǎn)方法，就可以刪除要?jiǎng)h除的下個(gè)結(jié)點(diǎn)了。

參考

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

本文轉(zhuǎn)載自微信公眾號(hào)「碼上積木」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼上積木公眾號(hào)。


網(wǎng)站名稱：LeetCode題解之刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)
網(wǎng)頁(yè)網(wǎng)址：http://www.dlmjj.cn/article/cdiphgh.html