leetcode19删除链表的倒数第 N 个结点

本文主要讲解删除链表倒数第n个节点的要点与细节

c++与java代码如下，末尾

本题之前可以尝试leetcode203移除链表元素

具体要点：

1.首先，单看移除链表节点，核心操作是:

cur->next = cur->next->next

 即，当前节点cur的下一个节点指向原本的下下个节点

小细节：操作时，我们需要得到要删除节点的上一个节点（cur），基于cur进行操作

2.其次，再考虑如何得到倒数第n个节点

这里笨办法可以遍历完链表，记录有多少个节点，把计算倒数第n个，换成计算正数第几个

但是我们学习一个比较好的办法：

        使用快慢指针（双指针），都先指向dummyHead，先让快指针fast移动n个节点，这样slow和fast之间就相差n，当fast到达末尾时，slow就表示从尾部数n个数，也就是倒数第n个节点

3.这里仍然使用链表中常用操作dummyHead虚拟指针，再讲一下dummyHead的作用：

        即：链表操作中，我们要操作某个节点n时，通常需要操作的是前一个节点n-1，而对于头节点我们要构造一个虚拟头节点，以便我们不用单独考虑头节点的特殊情况

4.小细节：

        我们考虑一下，当fast移动n个节点后，我们开始一起移动slow与fast，当fast==null时停止，此时slow指向需要删除的节点，但是我们具体操作是要获得这个节点的前一个节点，然后才能通过->next方法得到要删除的节点。（3中思想）

        解决方法：开始时我们让fast多移动一个节点，即移动n++个节点，这样slow后面就可以少移动一个节点，得到要删除的前一个节点。

c++代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        n++;
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while (n-- && fast!=nullptr) {
            fast = fast->next;
        }
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummyHead->next;
    }
};

java代码如下：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //新建头节点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        //新建快慢指针
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;
        n++;
        //遍历n，fast指向下一个
        while (n > 0 && fast != null) {
            fast = fast.next;
            n--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyHead.next;
    }
}