19、Remove Nth Node From End of List

Example

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

Output 1->2->3->5->null.

思路

首先建立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，结束。

解法

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;
    }
}