[[380272]]

前言

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

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

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

給你一個鏈表，刪除鏈表的倒數(shù)第 n 個結(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ù)組一樣，遍歷鏈表找到那個要被刪除的結(jié)點(diǎn)，所以先解決兩個問題：

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é)點(diǎn)就行了。

tempNode.next=tempNode.next.next; 

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

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

所以要把指針提前到第一個結(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); 
        //新建一個新的鏈表結(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; 
    } 
} 

時間復(fù)雜度

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

空間復(fù)雜度

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

解法二

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

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

比如這個題中，我們使用一個快指針一個慢指針，并且讓快指針快n個結(jié)點(diǎn)，然后兩個指針一直往后移動。當(dāng)快指針移動到結(jié)尾，那么慢指針的位置就是我們要刪除的結(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; 
    } 

時間復(fù)雜度

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

空間復(fù)雜度

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

其他解法

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

參考

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

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