puppy-dog-cute-love-cat-mammal
原文鏈接：https://wangwei.one/posts/java-algoDS-Remove-Nth-Node-From-End-of-List.html
前面，我們實現(xiàn)了 兩個有序鏈表的合并 操作，本篇來聊聊，如何刪除一個鏈表的倒數(shù)第N個節(jié)點。
刪除單鏈表倒數(shù)第N個節(jié)點
給定一個單鏈表，如: 1->2->3->4->5，要求刪除倒數(shù)第N個節(jié)點，假設(shè) N = 2，并返回頭節(jié)點。
則返回結(jié)果：1->2->3->5 .
解法一
這一題的難度標記為 medium，解法一比較容易想出來，我個人覺得難度不大。
思路
循環(huán)兩遍：
- 先遍歷一遍，求得整個鏈表的長度。
- 再遍歷一遍，當總長度
len減去n，恰好等于循環(huán)的下標i時，就找到對應(yīng)要刪除的目標元素，將prev節(jié)點與next節(jié)點連接起來即可。
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
int len = 0;
for(ListNode curr = head ; curr != null;){
len++;
curr = curr.next;
}
if(len == 0){
return null;
}
// remove head
if(len == n){
return head.next;
}
ListNode prev = null;
int i = 0;
for(ListNode curr = head; curr != null;){
i++;
prev = curr;
curr = curr.next;
if(i == (len - n)){
prev.next = curr.next;
}
}
return head;
}
}
Leetcode測試的運行時間為6ms，超過了98.75%的java代碼。
解法二
這種解法，比較巧妙，沒有想出來，查了網(wǎng)上的解法，思路如下：
思路
只需要循環(huán)一遍，定義兩個指針，一個快指針，一個慢指針，讓快指針的巧好領(lǐng)先于慢指針n步。當快指針到達tail節(jié)點時，滿指針巧好就是我們需要刪除的目標元素。
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i < n; i++){
fast = fast.next;
}
if(fast == null){
return slow.next;
}
ListNode prev = null;
for(ListNode curr = slow; curr != null; ){
// when fast arrived at tail, remove slow.
if(fast == null){
prev.next = curr.next;
break;
}
prev = curr;
curr = curr.next;
// move fast forward
fast = fast.next;
}
return head;
}
}
這段代碼在LeetCode上的測試結(jié)果與解法一的一樣。
這種解法與之前的 鏈表環(huán)檢測 題目中都使用到了快慢指針，用來定位特定的元素。
