Given a linked list, remove the nth node from the end of list and return its head.
原来的想法很简单，就是先扫描一遍list，判断list的长度，然后从头重新扫描，计算好走多少不，找到要删除的node的前一个node，然后把node.next = node.next.next; 这里需要对list扫描两次。
1 public ListNode removeNthFromEnd(ListNode head, int n) { 2 int length = 0; 3 ListNode tmp = head; 4 while (tmp != null) { 5 length++; 6 tmp = tmp.next; 7 } 8 if ( length < n ) return null; 9 else if (length == n ) { 10 if ( length == 1) return null; 11 else return head.next; 12 } 13 if ( n == 0 ) return head; 14 ListNode c = head; 15 for (int i=0; i<length-n-1; i++) { 16 c = c.next; 17 } 18 19 c.next = c.next.next; 20 21 return head; 22 }
在网上看到一种方法，不用扫描两次，只需一次。用两个指针，第一个指针先走n步，然后两个指针一起走。当走的快的那个指针到达null的时候，慢的指针恰好 指向需要删除的node的前一个node。而且代码更简洁。
1 public ListNode removeNthFromEnd(ListNode head, int n) { 2 // use two pointers,fast pointer forward n steps first 3 ListNode re=head,fast=head,slow=head; 4 for(int i=0;i<n;i++) fast=fast.next; 5 if(fast==null) return head.next; //head node need to be removed 6 while(fast.next!=null){ 7 fast=fast.next; 8 slow=slow.next; 9 } 10 slow.next=slow.next.next; 11 return head; 12 }
LeetCode: Remove Nth Node From End of List
原文：http://www.cnblogs.com/longhorn/p/3542223.html