题解 | #删除链表的倒数第n个节点#

题目的主要信息：

• 给定一个链表，要删除链表倒数第n个节点，并返回链表的头
• 题目保证链表长度一定大于等于$nn$

方法一：长度统计法

具体做法：

既然要删掉倒数第n个元素，那肯定得先找到这个元素，试想一下，如果是数组我们怎么找这个元素的？肯定是先统计数组长度$LL$，然后根据$L-nL-n$得到下标，再根据下标访问。但是很可惜，链表无法直接统计长度，也无法根据下标，我们能做的就是遍历链表。既然如此，那就两次遍历，第一次统计长度，第二次找到倒数第n个位置。

• step 1：给链表添加一个表头，处理删掉第一个元素时比较方便。
• step 2：遍历整个链表，统计链表长度。
• step 3：准备两个指针，一个指向原始链表头，表示当前节点，一个指向我们添加的表头，表示前序节点。两个指针同步遍历$L-nL-n$次找到倒数第$nn$个位置。
• step 4：前序指针的next指向当前节点的next，代表越过当前节点连接，即删去该节点。
• step 5：返回去掉添加的表头。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 0; //记录链表长度
        ListNode* res = new ListNode(-1); //添加表头
        res->next = head;
        ListNode* cur = head; //当前节点
        ListNode* pre = res; //前序节点
        while(cur != NULL){ //找到链表长度
            length++;
            cur = cur->next;
        }
        cur = head; //回到头部
        for(int i = 0; i < length - n; i++){ //从头遍历找到倒数第n个位置
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next; //删去倒数第n个节点
        return res->next; //返回去掉头节点
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表长度，最坏情况遍历整个链表2次
• 空间复杂度：$O(1)O(1)$，常数级指针，无额外辅助空间使用

方法二：双指针

具体做法：

我们无法逆序遍历链表，就很难得到链表的倒数第$nn$个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第$nn$的位置上，即距离链表尾的距离是$nn$，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是$nn$。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施：

• step 1：给链表添加一个表头，处理删掉第一个元素时比较方便。
• step 2：准备一个快指针，在链表上先走$nn$步。
• step 3：准备慢指针指向原始链表头，代表当前元素，前序节点指向添加的表头，这样两个指针之间相距就是一直都是$nn$。
• step 4：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数$nn$个元素的位置。

具体过程可以参考下列图示：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* res = new ListNode(-1); //添加表头
        res->next = head;
        ListNode* cur = head; //当前节点
        ListNode* pre = res; //前序节点
        ListNode* fast = head;
        while(n--) //快指针先行n步
            fast = fast->next;
        while(fast != NULL){ //快慢指针同步，快指针到达末尾，慢指针就到了倒数第n个位置
            fast = fast->next;
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next; //删除该位置的节点
        return res->next; //返回去掉头
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表长度，最坏情况遍历整个链表1次
• 空间复杂度：$O(1)O(1)$，常数级指针，无额外辅助空间使用