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;