LeetCode_19_中等_删除链表的倒数第N个结点

1. 题目

给你一个链表，删除链表的倒数第 $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]$

提示：

• $1<=sz<=30$，其中 $sz$ 为链表中的节点数目
• $0<=Node.val<=100$
• $1<=n<=sz$

2. 思路及代码实现（Python）

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 $\text{next}$ 指针指向链表的头节点。这样一来，就不需要对头节点进行特殊的判断了。

例如，在本题中，如果我们要删除节点 $y$，我们需要知道节点 $y$ 的前驱节点 $x$，并将 $x$ 的指针指向 $y$ 的后继节点。但由于头节点不存在前驱节点，因此我们需要在删除头节点时进行特殊判断。但如果我们添加了哑节点，那么头节点的前驱节点就是哑节点本身，此时我们就只需要考虑通用的情况即可。

题解引用来源：力扣官方题解

2.1 计算链表长度

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

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

该算法的时间复杂度为 $O(L)$，其中， $L$ 是链表的长度；空间复杂度为 $O(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

执行用时：44 ms
消耗内存：16.45 MB

2.2 栈

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 $n$ 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

上一个方法用链表结构，存储每个节点的指向节点，因此节省存储空间，无需存储所有的节点。而用栈的方法，在Python中用元素带顺序的列表来表征进出操作，实现逻辑很直观简单，但需牺牲部分存储空间。

该算法的时间复杂度为 $O(L)$，空间复杂度也为 $O(L)$。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        stack = list()
        cur = dummy
        while cur:
            stack.append(cur)
            cur = cur.next
        
        for i in range(n):
            stack.pop()

        prev = stack[-1]
        prev.next = prev.next.next
        return dummy.next

执行用时：27 ms
消耗内存：16.38 MB