去掉倒數(shù)第n的節(jié)點

題目

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list

becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass.

分析

題目說明了n總是合法的，并且建議我們用一次遍歷完成。題目中給出的節(jié)點類如下：

這是寫節(jié)點可以構(gòu)成一個單向鏈表，所以無法回頭！

算法

采用兩個引用，一快一慢，中間的間隔為給出的n，所以當(dāng)快的那個到了末尾，那么慢的那個的下一個元素就指向了要去除的元素了。 雖然看起來挺簡單，但是實現(xiàn)起來并不容易，邊界條件還是比較多的，但是我寫完之后看了下面那個代碼，我就發(fā)現(xiàn)，真是太機智了！

代碼

他在開始新建了一個節(jié)點，所以避免了很多不必要的特殊條件的判斷。大家可以自己嘗試一下，然后自己輸入一些數(shù)據(jù)驗證一下。