[[380272]]

前言

今天繼續說鏈表常見問題中的——刪除鏈表倒數第n個結點：

• 單鏈表反轉
• 兩個有序的鏈表合并
• 刪除鏈表倒數第n個結點
• 求鏈表的中間結點
• 鏈表中環的檢測

題目：刪除鏈表倒數第n個結點

給你一個鏈表，刪除鏈表的倒數第 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]

解法一

首先容易想到的辦法就是想數組一樣，遍歷鏈表找到那個要被刪除的結點，所以先解決兩個問題：

1、獲取鏈表的總長度

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

2、找到結點之后，怎么刪除。

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

tempNode.next=tempNode.next.next; 

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

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

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

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

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

時間復雜度

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

空間復雜度

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

解法二

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

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

比如這個題中，我們使用一個快指針一個慢指針，并且讓快指針快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; 
    } 

時間復雜度

時間復雜的為O(n)

空間復雜度

空間復雜度為O(1)

其他解法

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

參考

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

本文轉載自微信公眾號「碼上積木」，可以通過以下二維碼關注。轉載本文請聯系碼上積木公眾號。