给定一个链表，删除链表的倒数第 N 个节点，并返回头节点。

举例：
给定的链表：1->2->3->4->5，n = 2。
在删除倒数第二个节点之后，链表变成了 1->2->3->5。

提示： 给定的 n 总是有效。你能只扫描一次链表来完成吗？

/*
 * 19. Remove Nth Node From End of List
 * https://leetcode.com/problems/remove-nth-node-from-end-of-list/
 * https://www.whosneo.com/19-remove-nth-node-from-end-of-list/
 */

public class RemoveNthFromEnd {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node = head;
        node.next = new ListNode(2);
        node = node.next;
        node.next = new ListNode(3);
        node = node.next;
        node.next = new ListNode(4);
        node = node.next;
        node.next = new ListNode(5);

        RemoveNthFromEnd solution = new RemoveNthFromEnd();
        node = solution.removeNthFromEnd(head, 2);
        solution.print(node);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0), fast = dummyHead, slow = dummyHead;
        dummyHead.next = head;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummyHead.next;
    }
}