文章目錄
- 前言
- 題目
- 解題思路
- 代碼書寫程序
- 第一步 寫一個計算鏈表的節點個數的方法
- 第二步： 思考如何洗掉倒數 第 N 個 節點
- 首先設定 兩個參考 cur（代替head去遍歷鏈表），prev（表示前驅節點）
- 再思考一件事，如果洗掉的元素，剛好的是第一個元素的情況，（這是細節）
- 代碼實作
- 后面就是洗掉節點的正常情況了
- 代碼實作
- 接下來洗掉節點就簡單了，利用 "跨越式" 洗掉節點的方式來實作，也就是一句代碼，最后回傳 head 頭參考就行了！
- 最后附上程式
前言
如果有朋友看完本博客，還不清楚的，一定是鏈表的基礎不牢！ 建議看看這篇順序表 和 鏈表 - 單向鏈表部分文章，再來看這題，
?
題目
?
解題思路
首先我們要明白這是鏈表，不是順序表！鏈表是沒有下標的！ 所以我們第一步就是要去計算鏈表節點大的個數，
第二步:了解 單向鏈表洗掉節點的方法：借助洗掉節點的前驅節點來實作跨越式洗掉，就這兩步，細節的地方我們來看代碼，
?
代碼書寫程序
第一步 寫一個計算鏈表的節點個數的方法
?
第二步： 思考如何洗掉倒數 第 N 個 節點
我們這題是單向鏈表，所以是無法像雙向鏈表那樣，不需要借助其他節點，這也是為什么一開始我就在說單向鏈表洗掉節點的方法，
首先設定 兩個參考 cur（代替head去遍歷鏈表），prev（表示前驅節點）
prev 初始化為 null，是為了讓它比 cur 少走一步
?
再思考一件事，如果洗掉的元素，剛好的是第一個元素的情況，（這是細節）
代碼實作
?
后面就是洗掉節點的正常情況了
問題在于 如何 讓 cur 走到 洗掉節點節點位置，這樣我們prev就剛好在洗掉的節點的前面，
來看例子：
代碼實作
cur 每走一步，是不是就離洗掉的節點進一步？那么就意味著 鏈表的總節點個數 減去 要洗掉節點的倒數位置 的結果就少 1 ！
cur 和 洗掉節點關系更進一步了嘛，
不知道你們有沒有注意到一個細節： 我們的洗掉節點的前驅節點 prev，在 cur 移動之前，記錄了 cur 原先位置，也就是說 當cur 指向洗掉節點時，prev 剛好就在洗掉節點的前面！！！
?
接下來洗掉節點就簡單了，利用 “跨越式” 洗掉節點的方式來實作，也就是一句代碼，最后回傳 head 頭參考就行了！
?
最后附上程式
class Solution {
public static int size(ListNode h){
int count = 0;// 記錄鏈表的節點個數
while(h!=null){// 遍歷 鏈表
count++;
h = h.next;
}
return count;
}
public ListNode removeNthFromEnd(ListNode head, int n) {
int len = size(head);
ListNode cur = head;
ListNode prev = null;
if(n == len){
head = head.next;
}else{
while(len - n > 0){
prev = cur;
cur = cur.next;
len--;
}
prev.next = cur.next;
}
return head;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/385581.html
標籤：java
上一篇：java網路編程