0019：删除链表的倒数第 N 个结点（★）

力扣第 19 题

题目

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

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

相似问题：

• 1721：交换链表中的节点（1386 分）
• 1474：删除链表 M 个节点之后的 N 个节点
• 2095：删除链表的中间节点（1324 分）

分析

• 可以直接遍历得到总结点数，再定位倒数第 n 个结点，删除即可
• 要求一趟扫描，可以用经典的快慢指针解法：
  • 一开始快慢指针都指向哑结点
  • 快指针先走 n+1 步
  • 两个指针同时走直到快指针到空
  • 这时慢指针指向的就是倒数第 n+1 个结点

解答

1
2
3
4
5
6
7
8
9

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dum=slow=fast=ListNode(next=head)
        for _ in range(n+1):
            fast = fast.next
        while fast:
            slow,fast = slow.next,fast.next
        slow.next = slow.next.next
        return dum.next

时间 O(N)，42 ms