Problem

Given a linked list, remove the nth node from the end of list and return its head.

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.

Challenge

Can you do it without getting the length of the linked list?

Note

首先建立dummy结点指向head，复制链表。
然后建立快慢指针结点fast、slow，让fast比slow先走n个结点，再让fast和slow一起走，直到fast到达链表最后一个结点。由于fast比slow快n个结点，所以slow正好在链表倒数第n+1个结点。
最后让slow指向slow.next.next，就删除了原先的slow.next———倒数第n个结点。
返回dummy.next，结束。

Solution

public class Solution {
    ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0), slow, fast;
        dummy.next = head;
        fast = slow = dummy;
        while (n-- > 0) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}