/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: The head of linked list.
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //move the first pointer to nth position
        ListNode first = head;
        while(n>0){
            n--;
            first = first.next;
        }

        //special case: when the n is the legnth of the list: delete the first node straight away
        if(first==null) return head.next;
        /* can also add a dummy head before head:
        ListNode result = new ListNode(0);
        result.next = head;
        ...
        //at the end:
        return result.next;
        */

        //if not, move first and second together to find the nth last node and remove
        ListNode second = head;
        ListNode prev = result;
        while(first!=null){
            prev = second;
            first=first.next;
            second=second.next;
        }
        prev.next = second.next;
        return result.next;
    }
}