【LeetCode Hot 100】19. 删除链表的倒数第N个结点

题目描述

由于单向链表只能从头往后遍历，所以无法向数组那样的随机存取结构一样进行下标运算，也无法从链表尾向前数n个结点。本题有两个思路，个人觉得都比较简单。

1. 可以先遍历一遍链表得到链表的长度len，然后再从头往后数len - n个结点就是所求结点。
2. 可以使用快慢指针，快指针先移动n个结点，然后两个指针一起移动，直到快指针到达链表尾，此时慢指针指向的就是所求结点。

注意这种链表题可以考虑在链表头借助一个dummy结点，通过将该结点视作结点0，可以让第一个结点的行为与后续结点保持一致。

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