19. 刪除鏈表的倒數第 N 個結點 - 力扣（LeetCode）

1.暴力法

思路

（1）先獲取鏈表的長度L

（2）然后再次遍歷鏈表到L-n的位置，直接讓該指針的節點指向下下一個即可。

2.哈希表

思路

（1）將鏈表中所有節點都加入到哈希表中，其中哈希表的格式為HashMap<Integer,ListNode>,前面表示節點的位置，后面是節點。

（2）根據（1）可以知道鏈表的總長度nums，倒數第n個節點的位置為del=nums-n+1；

（3）然后取出del-1與del+1位置的節點，讓del-1的下一個節點為del+1即可。

ps：需要考慮被刪除的節點是否開頭節點或者結尾節點。開頭直接下一個，結尾直接del-1指向null即可。

具體代碼

/*** 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) {ListNode init = head;HashMap<Integer,ListNode> map =new HashMap<>();int count=0;while(head!=null){map.put(++count,head);head=head.next;}int nums=count;int del=nums-n+1;if(del==1){return init.next;}if(del==nums){if(nums==1){return new ListNode();}else{ListNode p1 = map.get(del-1);p1.next=null;return init;}}ListNode p1 = map.get(del-1);ListNode p2 = map.get(del+1);p1.next=p2;return init;}
}

3.棧

思路

（1）將全部節點入棧。

（2）然后用for循環彈出去n個節點，然后讓最后的節點的next等于next.next

ps：初始化的時候設置一個空節點指向head，防止全部彈出去后next.next報錯.

具體代碼

/*** 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) {ListNode init = new ListNode(0,head);Deque<ListNode> stack = new LinkedList<ListNode>();ListNode cur = init;while(cur!=null){stack.push(cur);cur=cur.next;}for(int i=0;i<n;i++){stack.pop();}ListNode n1 = stack.peek();n1.next=n1.next.next;return init.next;}
}

4.雙指針

思路

設計快慢指針，其中快指針比慢指針多走n次，等快指針到null的時候，慢指針所在的位置就是要彈出的位置的前一個

ps:（1）其實多走了n+1步，因為需要慢指針走到要彈出位置的前一個節點。

（2）慢指針是0節點并指向第一個節點head，快指針一開始就指向head，這樣就算長度為1的鏈表，slow慢指針的next.next也不會報錯，否則出現空指針異常。

具體代碼

/*** 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) {ListNode init = new ListNode(0,head);ListNode fast = head;ListNode slow = init;for(int i=0;i<n;i++){fast=fast.next;}while(fast!=null){fast=fast.next;slow=slow.next;}slow.next=slow.next.next;return init.next;}
}