力扣 19 删除链表的倒数第N个节点

题意：给一个链表，删除倒数第N个节点

思路：

1. 给链表添加一个新的头节点，以便返回时，能方便取到原始头节点
2. 取一个快指针指向新的头节点，把它向后移动N个节点
3. 取一个慢指针指向新的头节点，把它和此时的快指针一起向后移动，每次均移动一格，直到快指针的下一个节点为空则停止
4. 此时慢指针的下一个节点即为要移除的节点，可以让慢指针指向的节点，指向需要移除节点的下一个节点，并返回原始头节点

思想：快慢指针

复杂度：时间O（n)，空间O(1)

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        ListNode run1 = newhead;
        for(int i=0;i<n;i++)
            run1 = run1.next;
        ListNode run2 = newhead;
        while(run1.next != null) {
            run1 = run1.next;
            run2 = run2.next;
        }
        run2.next = run2.next.next;
        return newhead.next;
    }
}