重点是如何定位倒数第N个结点

删除倒数第N个结点,可以使用快慢指针来做。
快指针比慢指针先跑N个结点,当快指针刚好走到尽头(遇到null时),慢指针正好指向要删除的结点。

本方法设置了头结点dummy,还有慢指针pre,快指针head。
计划是让head先走n步,然后pre和head一起向前走,当head走到尽头的时候,pre的next正好指向要删除的结点。
注意细节即可。

为什么要设置头结点?万一这倒数第n个结点刚好是head指向的结点,这操作就有点麻烦了。总的来说头结点就是方便操作的。

class Solution {
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        // 先跑n步
        for(int i = 0;i < n;i++){
            head = head.next;
        } 
        // 计划是,head在前面走到尽头,此时pre正好处于要修改的结点的前一个
        while(head != null){
            head = head.next;
            pre = pre.next;
        }
        // 删掉倒数第n个结点
        pre.next = pre.next.next;
        // 设置头结点,考虑的是,万一要删除的是第一个结点,不方便操作
        return dummy.next;
    }
}