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

题目

19. 删除链表的倒数第 N 个结点（中等）

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

示例：

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

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

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

数据范围：链表长度 1 ≤ sz ≤ 30，0 ≤ Node.val ≤ 100，1 ≤ n ≤ sz

进阶：你能尝试使用一趟扫描实现吗？

思路

通用技巧：添加哑节点（dummy），next 指向头节点。头节点的前驱就是 dummy，删除时无需对头节点特判。

方法一：计算链表长度

先遍历一遍得到长度 L，再从哑节点走 L−n+1 步（节点从 1 计数），当前节点的下一个节点就是待删节点，修改一次指针即可。

方法二：栈

所有节点依次入栈，根据「先进后出」弹出 n 个节点后，栈顶就是待删节点的前驱。

方法三：双指针

first 先走 n 步，然后 first 与 second（从 dummy 出发）同速前进；first 到达末尾时，second.next 恰好是待删节点。一趟扫描，常数空间。

方法四：递归

递归返回「当前节点是倒数第几个」（k = fun(node.next) + 1）；回溯时当 k == 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)，空间复杂度 O(1)

方法二：栈

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

• 时间复杂度 O(L)，空间复杂度 O(L)（栈的开销）

方法三：双指针

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)
        l = dummy
        r = head
        for i in range(n):
            r = r.next
        while r:
            r = r.next
            l = l.next
        l.next = l.next.next
        return dummy.next

• 时间复杂度 O(L)，空间复杂度 O(1)

方法四：递归

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)

        def fun(node):
            if not node:
                return 0
            k = fun(node.next) + 1
            if k == n + 1:
                node.next = node.next.next
            return k

        fun(dummy)
        return dummy.next

• 时间复杂度 O(L)，空间复杂度 O(L)（递归栈深度）