LeetCode題解之如何刪除鏈表倒數第n個結點

這篇文章主要講解了“LeetCode題解之如何刪除鏈表倒數第n個結點”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“LeetCode題解之如何刪除鏈表倒數第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;     }

感謝各位的閱讀，以上就是“LeetCode題解之如何刪除鏈表倒數第n個結點”的內容了，經過本文的學習后，相信大家對LeetCode題解之如何刪除鏈表倒數第n個結點這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！