[Leetcode 19] 删除链表的倒数第 N 个节点

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给你一个链表,删除链表的倒数第 n 个节点,并且返回链表的头节点。
示例 1:
notion image
示例 2:
示例 3:
提示:
  • 链表中节点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz
 
 

解法一:两次遍历

  1. 第一次遍历: 计算链表有多少个节点
  1. 第二次遍历: 从 dummy 节点走到第 L - n 个节点, 这个节点就是倒数第 n 个节点的前一个节点prev
  1. 找到prev之后,删除就很简单 prev.next = prev.next.next
复杂度
  • 时间:O(n)
  • 空间:O(1)

解法二:一趟遍历(快慢指针)(推荐)

让 first 指针先走 n 步。然后让 slow 指针 和 first指针 一起走。
这样当 first 抵达链表末尾时,slow 就在倒数第 n+1 个节点(即要删节点的前一个节点)。
复杂度
  • 时间:O(n)
  • 空间:O(1)

解法三:栈

  • 遍历链表,把每个节点都“压栈”,
  • 连续弹 n 次就找到倒数第 n 个节点的前一个,
  • 执行删除。
复杂度
  • 时间:O(n)
  • 空间:O(n)(栈存放所有节点)

解法四:递归(回溯计数)

递归到链表尾部, 然后回溯并计数回到尾的距离。
相当于用递归栈模拟链表的逆序遍历。
在“回来的路上”数到第 n 个节点,然后删除它。
复杂度
  • 时间:O(n)
  • 空间:O(n) 递归栈
上一篇
[Leetcode 18] 四数之和
下一篇
[Leetcode 20] 有效的括号