題目

給定一個鏈表，刪除鏈表的倒數(shù)第 n 個結(jié)點，并且返回鏈表的頭結(jié)點。

示例 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]

提示：

??? 鏈表中結(jié)點的數(shù)目為 sz
??? 1 <= sz <= 30
??? 0 <= Node.val <= 100
??? 1 <= n <= sz （n符合規(guī)范，題目中不用判斷其合法性）

進階：能嘗試使用一趟掃描實現(xiàn)嗎？

---

思路

此題與上一題類似，采用快慢指針法。不同的是，此題的slow和fast兩個快慢指針都是從dummyHead虛擬頭節(jié)點開始向后走，這樣可以確保當fast指向null時，slow恰好指向待刪除節(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) {if(head == null) {return null;}ListNode dummyHead = new ListNode(-1);dummyHead.next = head;//采用快慢指針法先找到鏈表中倒數(shù)第n個節(jié)點ListNode slow = dummyHead, fast = dummyHead;//先讓fast走n步for(int i = 0; i < n + 1; i++) {if(fast == null) {return head;}fast = fast.next;}//讓slow和fast一起向后走while(fast != null) {slow = slow.next;fast = fast.next;}//此時slow就指向了待刪除節(jié)點的前一個節(jié)點，刪除要刪的節(jié)點即可slow.next = slow.next.next;return dummyHead.next;}
}