LeetCode題解之如何刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)

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

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

題目：刪除鏈表倒數(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è)問題：

1、獲取鏈表的總長度

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

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

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

tempNode.next=tempNode.next.next;

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

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

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

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

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

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

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

空間復(fù)雜度

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

解法二

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

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

比如這個(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)被刪除的情況，所以要把開始結(jié)點(diǎn)提前到鏈表之前。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個(gè)結(jié)點(diǎn)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)LeetCode題解之如何刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

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

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

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

猜你還喜歡下面的內(nèi)容