這篇文章主要講解了“LeetCode題解之如何刪除鏈表倒數(shù)第n個結(jié)點”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“LeetCode題解之如何刪除鏈表倒數(shù)第n個結(jié)點”吧！

創(chuàng)新互聯(lián)建站主要從事網(wǎng)站制作、成都做網(wǎng)站、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)石鼓,十多年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575

題目：刪除鏈表倒數(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、獲取鏈表的總長度

public int getLength(ListNode head){         int n=0;         while(head!=null){             n++;             head=head.next;         }         return n;     }

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

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

tempNode.next=tempNode.next.next;

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

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

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

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

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode() {}  *     ListNode(int val) { this.val = val; }  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  * }  */ class Solution {     public ListNode removeNthFromEnd(ListNode head, int n) {         int length=getLength(head);         //新建一個新的鏈表結(jié)點指向head頭結(jié)點，也就是上面要注意的特殊情況         ListNode lastNode=new ListNode(0,head);         ListNode tempNode=lastNode;         for(int i=0;i<length-n;i++){             tempNode=tempNode.next;         }         tempNode.next=tempNode.next.next;         return lastNode.next;     }      public int getLength(ListNode head){         int n=0;         while(head!=null){             n++;             head=head.next;         }         return n;     } }

時間復(fù)雜度

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

空間復(fù)雜度

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

解法二

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

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

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

當然，這里也要考慮到當前結(jié)點被刪除的情況，所以要把開始結(jié)點提前到鏈表之前。public ListNode removeNthFromEnd(ListNode head, int n) {  //提前鏈表         ListNode LastNode=new ListNode(0,head);         ListNode FirstNode=LastNode;         ListNode SecondNode=head;         for(int i=0;i<n;i++){             SecondNode=SecondNode.next;         }          while(SecondNode!=null){             FirstNode=FirstNode.next;             SecondNode=SecondNode.next;         }          FirstNode.next=FirstNode.next.next;                  return LastNode.next;     }

感謝各位的閱讀，以上就是“LeetCode題解之如何刪除鏈表倒數(shù)第n個結(jié)點”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對LeetCode題解之如何刪除鏈表倒數(shù)第n個結(jié)點這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！

文章題目：LeetCode題解之如何刪除鏈表倒數(shù)第n個結(jié)點
文章URL：http://aaarwkj.com/article14/iidoge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、網(wǎng)頁設(shè)計公司、域名注冊、手機網(wǎng)站建設(shè)、網(wǎng)站排名、用戶體驗

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)