日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

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

新聞中心

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

前言

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

今天繼續(xù)說鏈表常見問題中的——刪除鏈表倒數(shù)第n個結(jié)點：

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

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

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

進階：你能嘗試使用一趟掃描實現(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ù)組一樣，遍歷鏈表找到那個要被刪除的結(jié)點，所以先解決兩個問題：

1、獲取鏈表的總長度

 
 
 
 
    
  
  
  
  
  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é)點之后，怎么刪除。

其實就是把next指向跨過去要刪除的結(jié)點就行了。

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

但是，上述這個方法是刪除的tempNode.next結(jié)點，如果我們要刪除tempNode本身這個結(jié)點，那么就要把一開始的結(jié)點提前到第一個結(jié)點之前。

比如我們要刪除鏈表的第一個結(jié)點，如果你本身的指針就指向第一個結(jié)點，那么通過上面這個刪除方法就永遠刪除不了第一個結(jié)點了。

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

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

 
 
 
 
    
  
  
  
  
  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.         //新建一個新的鏈表結(jié)點指向head頭結(jié)點，也就是上面要注意的特殊情況 
    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.

時間復雜度

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

空間復雜度

只用到幾個單獨的鏈表結(jié)點，所以空間復雜度為O(1)

解法二

再想想，可不可以不計算鏈表長度呢?也就是題目上所說的進階解法，用一次掃描。

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

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

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

 
 
 
 
    
  
  
  
  
  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.

時間復雜度

時間復雜的為O(n)

空間復雜度

空間復雜度為O(1)

其他解法

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

參考

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

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


文章標題：LeetCode題解之刪除鏈表倒數(shù)第n個結(jié)點
轉(zhuǎn)載源于：http://www.5511xx.com/article/cdiphgh.html