Remove Nth Node From End of List

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.

算法：删除单链表的节点一定要找到其前驱节点。

思路1：先求出list的长度，从而在遍历的时候可以计数，通过计数从而找到其前驱节点，空间时间复杂度都是O(n)，但是两次遍历，计算list长度的时候，第二遍遍历的时候。

比较简单，不再实现了。

思路2，双指针，让第二个指针先走n步，然后齐步走，第二个指针走到底的时候，第一个指针刚好停在其前驱，一次遍历

代码如下：

 1 public class Solution { 2     public ListNode removeNthFromEnd(ListNode head, int n) { 3         ListNode hhead = new ListNode(0); 4         hhead.next = head; 5         ListNode one = hhead; 6         ListNode two = hhead; 7         for(int i = 0; i < n; two = two.next,i++); 8         while(two.next != null){ 9             one = one.next;10             two = two.next;11         }12         one.next = one.next.next;13         return hhead.next;14     }15 }

链表题，双指针真的很常用，甚至是三指针，这道题是很经典的面试题，只不过本题把难度限制了，比如n的大小范围合法，默认list合法等