題目
給定一個鏈表喇勋，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點偎行。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后川背，鏈表變?yōu)?1->2->3->5.
說明：
給定的 n 保證是有效的。
進階：
你能嘗試使用一趟掃描實現(xiàn)嗎睦优？
頭節(jié)點的應用
（引用百度百科）
講到鏈表不得不講到頭節(jié)點渗常，數(shù)據(jù)結(jié)構(gòu)中，在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點汗盘，它沒有直接前驅(qū)皱碘，稱之為頭結(jié)點
頭結(jié)點是鏈表里面第一個結(jié)點，他的數(shù)據(jù)域可以不存放任何信息（有時候也會存放鏈表的長度等等信息）隐孽，他的指針區(qū)域存放的是鏈表中第一個數(shù)據(jù)元素的結(jié)點（就是傳說中的首元結(jié)點）存放的地址癌椿。
- 防止單鏈表是空的而設(shè)的.當鏈表為空的時候,帶頭結(jié)點的頭指針就指向頭結(jié)點.如果當鏈表為空的時候,頭結(jié)點的指針域的數(shù)值為NULL.
- 是為了方便單鏈表的特殊操作,插入在表頭或者刪除第一個結(jié)點.這樣就保持了單鏈表操作的統(tǒng)一性!
- 單鏈表加上頭結(jié)點之后健蕊，無論單鏈表是否為空，頭指針始終指向頭結(jié)點踢俄，因此空表和非空表的處理也統(tǒng)一了缩功，方便了單鏈表的操作，也減少了程序的復雜性和出現(xiàn)bug的機會 都办。
思路
- 鏈表的結(jié)構(gòu)特殊嫡锌，沒有辦法根據(jù)倒數(shù)位置直接定位到該位置的具體索引值，因為事先不知道鏈表的長度琳钉，如果設(shè)置一個快指針和慢指針势木，令他們的的距離為n，然后一起滑動歌懒，這樣啦桌，當快指針到達終點的時候，慢指針下一個指向剛好就行需要刪除的節(jié)點
- 設(shè)置一個頭指針preNode,preNode.next=head
- 設(shè)置快指針fastNode=preNode,慢指針slowNode=preNode
- 循環(huán)n次及皂，讓fastNode前進n步
- 繼續(xù)循環(huán)甫男，直到fastNode到達鏈表尾端，這樣慢節(jié)點的下一個節(jié)點剛好就是要刪除的節(jié)點
圖解
用ppt做的gif
圖解算法.gif
代碼
public class removeNthFromEnd {
public ListNode removeNthFromEndSolution(ListNode head, int n) {
ListNode preNode = new ListNode(0);
preNode.next = head;
ListNode fastNode = preNode, slowNode = preNode;
while (n > 0) {
fastNode = fastNode.next;// 采用快慢節(jié)點
n--;
}
while (fastNode.next != null) {
fastNode = fastNode.next;
slowNode = slowNode.next;// 快慢節(jié)點距離始終一致验烧，等快節(jié)點到終點的時候板驳，慢節(jié)點剛好落在了需要刪除的那個節(jié)點上面
}
slowNode.next = slowNode.next.next;// 刪除節(jié)點
return preNode.next;
}
}
