Remove the Nth Node from end of List

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.

難點： 你不知道這個list總共多長，如果只能一次pass的話，怎么知道倒數(shù)第幾個在哪?

這個是一個很巧妙的雙指針類型題目。

假設(shè)我們有兩個指針，一個跑的快，一個跑的慢。假設(shè)兩者跑步速度一樣快，但是出發(fā)的時候快指針比滿指針早出發(fā)n步。 那么快指針到end of List的時候，慢指針就剛好在倒數(shù)第n個node。

還有Tricky的點在于： 要設(shè)立一個fake node. 這個算是一個edge case, 假設(shè) ?1->null. remove 倒數(shù)第一個node。 那么很不好辦， 因為fast 指針跑到Null那個位置，slow指向1的話 ?沒辦法返回去一個Null list。你總不能讓slow自己cancel自己吧。 所以只能用一個fake node來解決這個問題。

也就是，我們的起跑線不從第一個node開始，而是從fake node開始。

ListNode start = new ListNode(0);

ListNode slow = start, fast = start;

slow.next = head;