/*
1. 题意为只扫描一次并找出倒数第 n 个节点的前一个节点
2. 因为只扫描一次，不能先求长度 -> 只要知道距 end n+1 个节点的位置 -> 双指针
3. 因为可能要删除 head，所以在 head 前建一个『虚拟节点』，结果为虚拟节点的next
*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode prev = new ListNode(9);
        prev.next = head;

        ListNode left = prev;
        ListNode right = prev;

        while (n-- != 0) {
            right = right.next;
        }

        while (right.next != null) {
            left = left.next;
            right = right.next;
        }

        left.next = left.next.next;

        return prev.next;
    }
}



/** 
1. The key to problem is how to find nth node from the ena of list.
1.1. We can't know how many nodes there are in the linklist, but we easy to know nth node for the list head;
1.2. This can determint a segment that have length is n
1.3. we can move the segemnt to the end of list, and then the other endpoint of segment is the nth noed of the end of list.

2. another point is how to delete it.
2.1 do a deep copy like NthNode = NthNode.next;

*/
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode left = head;
        ListNode right = head;

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

        if (right == null) {
            return head.next;
        }

        while (right.next != null) {
            left = left.next;
            right = right.next;
        }

        ListNode nth = left.next;

        if (nth == null) {
            return null;
        } else if (nth.next == null) {
            left.next = null;
        } else {
            nth.val = nth.next.val;
            nth.next = nth.next.next;
        }

        return head;
    }
}