T19. Remove Nth Node From End of List【Medium】
題目
給定一個(gè)鏈表蹭沛，從鏈表的末尾刪除第n個(gè)節(jié)點(diǎn)并返回它的頭霞怀。
例如吉殃，
給出鏈表: 1->2->3->4->5,以及 n = 2.
在移除了倒數(shù)第二個(gè)節(jié)點(diǎn)后, 鏈表變成了 1->2->3->5.
補(bǔ)充：
給出的 n 總是有效地
嘗試把這題一遍過
思路
① 首先建議不明白鏈表的先了解一下鏈表
② 代碼用start保存首節(jié)點(diǎn)酱鸭，用fast和slow結(jié)合起來尋找到目標(biāo)節(jié)點(diǎn)位置
③ 因?yàn)殒湵聿荒軓暮笸耙苿?dòng)劫樟，也不知道長度痪枫，所以先把 fast 前移 n，保持 slow 和 fast 的差值叠艳，把 fast 移動(dòng)到最后（也就是鏈表常用的 fast==null）,然后此時(shí) slow 就能容易的定位到倒數(shù)第n個(gè)數(shù)
④ 鏈表常用去節(jié)點(diǎn)方式：slow.next = slow.next.next; 下面舉個(gè)例子
鏈表 A->B->C 去掉B：A 放開 B 的尾巴奶陈，抓住 C 的尾巴
⑤ 具體看代碼以及注釋~
⑥ 有問題歡迎吐槽哈~
代碼
代碼取自 Top Solution，稍作注釋
/**
* 給出的ListNode的結(jié)構(gòu)
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//初始化一個(gè) val=0 的 ListNode ,并賦給 start,slow,fast
ListNode start = new ListNode(0);
ListNode slow = start, fast = start;
//把傳入的鏈表賦給slow.next
slow.next = head;
//把 fast 往前移動(dòng) n,使得fast和slow相差n
for(int i=1; i<=n+1; i++) {
fast = fast.next;
}
//把fast移動(dòng)到最后一個(gè), 保持slow一起移動(dòng)附较，相差不變吃粒，此時(shí)slow就是從后往前n
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
//通過這句代碼跳過中間的節(jié)點(diǎn)
slow.next = slow.next.next;
//start用來保存首節(jié)點(diǎn)，返回start.next就是首節(jié)點(diǎn)
return start.next;
}
}
補(bǔ)充
關(guān)于代碼中的,debug了一下拒课，slow 和 fast 的地址和 start 是一樣徐勃，所以是傳遞地址的，在后面改了任一一個(gè)其他的也會改早像。
ListNode start = new ListNode(0);
ListNode slow = start, fast = start;
可以看到地址是相同的（哎這個(gè)應(yīng)該是地址吧）~
