目录

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

进阶:你能尝试使用一趟扫描实现吗?

相似问题:

分析

  • 可以直接遍历得到总结点数,再定位倒数第 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