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的话，怎么知道倒数第几个在哪?

这个是一个很巧妙的双指针类型题目。

假设我们有两个指针，一个跑的快，一个跑的慢。假设两者跑步速度一样快，但是出发的时候快指针比满指针早出发n步。 那么快指针到end of List的时候，慢指针就刚好在倒数第n个node。

还有Tricky的点在于： 要设立一个fake node. 这个算是一个edge case, 假设  1->null. remove 倒数第一个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;