No.19 删除链表的倒数第 N 个结点 (Medium)

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
例如：
n = 2

思路

该题目的难点是只通过一趟扫描实现，如果没有该限制，则只需要遍历两次，第一次统计总结点数，第二次移除倒数第n个即可。

那么如何通过一次扫描实现呢？
利用双指针：

1. 初始化两个指针start和end指向dummy结点;
2. end往后移动n步；
3. start和end一起移动；
4. 当end指向最后一个结点时，start指向的结点就是要移除的结点的前一个结点 （注意不是指向要移除的结点，因为我们要操作前一个结点的指针）；
5. 移除start指向的下一个结点即可

例如，

1. 刚开始时，start和end都指向dummy;
2. end往后移动2步，指向2；
3. start和end一起移动；
4. 直到end指向5时， 此时start指向3，3后面的结点就是要移除的结点；
5. 移除3后面的4；

代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {    
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 注意要指向dummy，而非指向head，否则后面将出现空指针异常
        ListNode start = dummy;
        ListNode end = dummy;
        while (n > 0) {
            end = end.next;
            n--;
        }
        // 此处为start和end指向dummy的原因，例如输入为[1], 1，即移除倒数第1个结点
        // 如果start和end开始时指向head而非dummy, 那么在上面的循环中，end指向了null
        // 那么此处的end.next就会出现空指针异常.
        while (end.next != null) {
            start = start.next;
            end = end.next;
        }
        ListNode removedNode = start.next;
        start.next = removedNode.next;
        removedNode.next = null;
        return dummy.next;
    }
}

反思

在第一次的代码中，我让start和end初始化指向了head，导致第17行出现了空指针异常，当输入为[1]和1时，如下：

在end往后移动1步时，end指向了null, 因此在第17行

        while (end.next != null) {
            start = start.next;
            end = end.next;
        }

end.next出现空指针异常。
因此需要通过让start和end指向dummy来保证end移动n步后，最多指向最后一个结点，而非null结点。

这里也体现了dummy node的优势！