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.

Solution：Two pointers

One pass( no length precalc)
Time Complexity: O(N) Space Complexity: O(1)

Solution_a Code：
// with dummy startpoint

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // dummy -> 1  ->  2  ->  3  ->  4  ->  5  ->  null, n = 2
        //                      second    ---n+1---    first
        
        ListNode dummy = new ListNode(0);   // to deal with when n == list.length
        dummy.next = head;
        
        // init two pointers with n gap
        ListNode first = dummy, second = dummy;
        for(int i = 0; i < n + 1 && first != null; i++) {
            first = first.next;
        }
        
        // if(i < n + 1 && first == null) return null; // if n is not valid, but input is strict)
        
        // move the two ptrs until first one hits end
        while(first != null) {
            first = first.next;
            second = second.next;
        }
        
        // remove
        ListNode next = second.next;
        second.next = second.next.next;
        next.next = null;
        
        return dummy.next;
    }
}

Solution_b Code：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        // init two pointers with n gap
        ListNode first = head, second = head;
        for(int i = 0; i < n && first != null; i++) {
            first = first.next;
        }
        if(first == null) return head.next; // n == list.length, remove the first one  (or n is not valid, but input is strict)
        
        // move the two ptrs until first one hits end
        while(first.next != null) {
            first = first.next;
            second = second.next;
        }
        
        // remove
        ListNode next = second.next;
        second.next = second.next.next;
        next.next = null;
        
        return head;
    }
}

round1

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        for(int i = 0; i < n && fast.next != null; i++) {
            fast = fast.next;    
        }
        
        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // start deleting
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}