Remove Nth Node from End of List

Given a linked list, remove the n^th 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.

The key idea is to find the Nth node to the end of the list. Then the remaining things are easy. If we want to solve it in one pass, we should not use only one pointer. Therefore, we use two pointers, one moves earlier, which can reach the end of the list first, after n steps. Then the other starts to move.

01 public ListNode removeNthFromEnd(ListNode head, int n) {
02         if(n==0 || head==null)
03             return head;
04         ListNode fast=head;
05         while(n>0 && fast!=null)
06         {
07             fast=fast.next;
08             n--;
09         }
10         if(fast==null)
11         {
12             return head.next;
13         }
14         ListNode slow=head;
15         ListNode curr=slow;
16         while(fast!=null && fast.next!=null)
17         {
18             fast=fast.next;
19             curr=curr.next;
20         }
21         curr.next=curr.next.next;
22         return slow;
23     }