题目

标题和出处

标题：删除链表的倒数第 N 个结点

出处：19. 删除链表的倒数第 N 个结点

难度

3 级

题目描述

要求

给你一个链表，删除链表的倒数第 个结点，然后返回链表的头结点。

示例

示例 1：

输入：
输出：

示例 2：

输入：
输出：

示例 3：

输入：
输出：

数据范围

• 链表中结点的数目为
• 
• 
• 

进阶

你能使用一次遍历实现吗？

解法一

思路和算法

最直观的做法是，首先遍历链表得到链表的结点数量 ，然后再次遍历链表，找到待删除的结点并将其删除。当链表的结点数量是 时，删除倒数第 个结点等价于删除正数第 个结点。

当 时，待删除的结点为链表的头结点，因此返回 。

当 时，定位到待删除结点的前一个结点 ，然后将结点 删除。具体做法如下：

1. 结点 为链表的正数第 个结点，因此从 开始向后移动 次，即可得到结点 ；
2. 删除 的后一个结点，可通过改变 指针的指向实现，令 指向 即可。

如果待删除的结点是链表的最后一个结点，上述做法同样适用，在删除结点之后， 将指向 。

下图为示例 1 的删除结点的过程。此时 ，，待删除的结点是正数第 个结点，因此定位到正数第 个结点，然后令正数第 个结点的 指向正数第 个结点，完成删除操作。

代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int sz = 0;
        ListNode temp = head;
        while (temp != null) {
            sz++;
            temp = temp.next;
        }
        if (n == sz) {
            return head.next;
        }
        temp = head;
        int before = sz - n;
        for (int i = 1; i < before; i++) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
        return head;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28%5Ctextit%7Bsz%7D%29&id=x4heF)，其中 是链表的长度。最多需要遍历链表两次，删除结点的时间为 #card=math&code=O%281%29&id=DdNre)。
• 空间复杂度：#card=math&code=O%281%29&id=OFXvy)。

解法二

思路和算法

上述解法需要首先得到链表的结点数量 ，然后进行删除操作，因此需要两次遍历。其实，链表的结点数量 不需要事先知道，一次遍历也可以完成删除操作。

由于待删除的是倒数第 个结点，因此可以想到使用两个指针，这两个指针指向的结点在链表中相差 个位置。用 和 分别表示两个指针，其中 在 的后面 个位置。当 指向链表的最后一个结点时， 指向待删除结点的前一个结点。

由于待删除的结点可能是链表的头结点，因此需要创建哑节点 ，使得 。将两个指针 和 初始化为都指向 ，然后将 向后移动 次，即满足 在 的后面 个位置。

当 和 满足相差 个位置时，同时将两个指针向后移动，直到 指向链表的最后一个结点，此时 指向待删除结点的前一个结点。将 定位到待删除结点的前一个结点之后，令 指向 ，即可完成删除操作。

完成删除操作之后，新的头结点为哑节点的下一个结点，因此返回 。

下图为示例 1 的删除结点的过程，图中的灰色结点表示哑节点。此时 ，因此将 移动到和 相差 个位置，然后同时向后移动 和 ，直到 指向链表的最后一个结点， 指向待删除结点的前一个结点，删除 指向的结点的下一个结点。最后返回哑节点的下一个结点。

代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0, head);
        ListNode temp1 = dummyHead, temp2 = dummyHead;
        for (int i = 0; i < n; i++) {
            temp2 = temp2.next;
        }
        while (temp2.next != null) {
            temp1 = temp1.next;
            temp2 = temp2.next;
        }
        temp1.next = temp1.next.next;
        return dummyHead.next;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28%5Ctextit%7Bsz%7D%29&id=k9hR4)，其中 是链表的长度。需要遍历链表一次，删除结点的时间为 #card=math&code=O%281%29&id=QJkbD)。
• 空间复杂度：#card=math&code=O%281%29&id=PAhlt)。