题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

---

示例

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

---

提示：

链表中结点的数目为 sz

• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

---

思路及算法代码

思路

一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点。

为了与题目中的 n 保持一致，节点的编号从 1 开始，头节点为编号 1 的节点。

为了方便删除操作，我们可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。

代码

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 辅助函数：获取链表的长度
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        # 创建一个哑节点来处理需要移除头节点的特殊情况
        dummy = ListNode(0, head)
        length = getLength(head)  # 获取链表的长度
        cur = dummy  # 初始化指针指向哑节点
        # 遍历到待移除节点的前一个节点
        for i in range(1, length - n + 1):
            cur = cur.next
        cur.next = cur.next.next  # 跳过待移除节点
        return dummy.next  # 返回已修改的链表，不包括被移除的节点

复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。

• 空间复杂度：O(1)。

---

知识点

哑节点（dummy node）是指在链表操作中添加的一个虚拟节点，它不存储任何实际的数据，仅用作辅助操作。通常情况下，哑节点位于链表头部或尾部，用来处理一些边界情况，简化代码逻辑。

在链表操作中，哑节点常用于以下情况：

• 简化头节点的特殊处理： 在一些操作中，需要对头节点进行特殊处理，如插入、删除等操作。使用哑节点可以使得头节点的操作与其他节点一致，从而减少特殊情况的处理。

• 避免空指针异常： 在一些算法中，可能需要对链表进行遍历操作。使用哑节点作为头节点可以避免在遍历时遇到空链表的情况，简化代码的控制流程。

• 简化边界情况的处理： 在一些操作中，可能会涉及到处理边界情况，如移除倒数第N个节点等。使用哑节点可以统一处理边界情况，使得代码更加清晰和易于理解。

总的来说，哑节点是一种在链表操作中常用的技巧，能够简化代码逻辑，提高代码的可读性和可维护性。