LeetCode-Remove Nth Node From End of List

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

最直接的思路是使用一个 ListArray 将链表中每个指针都存储，这样可以直接把数组一样操作链表。

不过在提交的时候发现了一些边界值的问题，需要稍微注意一下。

/**
 * 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) {
        List<ListNode> lns=new ArrayList<>();
        while(head!=null){
            lns.add(head);
            head=head.next;
        }
        int s=lns.size();
        if(s<n || s==1) return null;
        if(s-n-1>=0){
            ListNode t=lns.get(s-n-1);
            if(t.next!=null) t.next=t.next.next;
            return lns.get(0==n?1:0);
        }else{
            return lns.get(1);
        }
    }
}

运行时间还不错，基本很快了。不过看了 Solution，发现居然有更快的办法和更好的解决边界值得办法。

可以使用两个指针，第一个指针向后移动 n 的距离，然后一起向后移动直到第一个指针移动到末尾，这时，第二个指向的就是将要被删除的元素的之前的一个元素，思路很棒！

另外就是如果在头部添加一个空元素，那么就可以避免在链表长度比较短的时候对很多情况的讨论。

/**
 * 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 flag=new ListNode(0);
        flag.next=head;
        ListNode first=flag,second=flag;
        for(int i=0;i<=n;i++) first=first.next;
        while(first!=null){
            first=first.next;
            second=second.next;
        }
        second.next=second.next.next;
        return flag.next;
    }
}