LeetCode【0019】删除链表的倒数第N个结点
本文目录
- 1 中文题目
- 2 求解方法:虚拟头节点和快慢指针
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
- 3 题目总结
1 中文题目
给定一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
示例:
链表如上:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
输入:head = [1], n = 1
输出:[]
输入:head = [1,2], n = 1
输出:[1]
提示:
- 链表中结点的数目为
sz
- 1 ≤ s z ≤ 30 1 \leq sz \leq 30 1≤sz≤30
- 0 ≤ N o d e . v a l ≤ 100 0 \leq Node.val \leq 100 0≤Node.val≤100
- 1 ≤ n ≤ s z 1 \leq n \leq sz 1≤n≤sz
2 求解方法:虚拟头节点和快慢指针
2.1 方法思路
方法核心
使用虚拟头节点统一操作逻辑,采用快慢指针确定删除位置,快指针先走n步,然后快慢指针同步移动,直到快指针到达末尾
实现步骤
- 创建虚拟头节点阶段:
- 新建值为0的虚拟节点
- 将虚拟节点指向原链表头部
- 初始化快慢指针阶段:
- 快慢指针都指向虚拟头节点
- 确保初始状态一致
- 快指针移动阶段:
- 快指针向前移动n步
- 建立n个节点的间隔
- 双指针同步移动阶段:
- 快慢指针同时向前移动
- 直到快指针到达链表末尾
- 删除目标节点阶段:
- 慢指针此时位于待删除节点的前一个位置
- 修改next指针完成删除操作
方法示例
输入:head = [1,2,3,4,5], n = 2
# 1. 初始状态:创建虚拟头节点,快慢指针都指向虚拟头节点
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑
fast
↑
slow
(dummy)# 2. 快指针先移动n=2步
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑ ↑
slow fast
(dummy)# 3. 快慢指针同时移动,直到快指针的next为NULL
# 移动过程中的状态:
# 第一步:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL↑ ↑slow fast# 第二步:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL↑ ↑slow fast# 第三步:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL↑ ↑slow fast# 4. 此时slow指向待删除节点(4)的前一个节点(3)
# 执行删除操作:slow.next = slow.next.next
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL↑ ↑slow fast变为:
0 -> 1 -> 2 -> 3 -----→ 5 -> NULL↑ ↑slow fast# 5. 最后返回dummy.next,即返回真实的头节点
1 -> 2 -> 3 -> 5 -> NULL
2.2 Python代码
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:# 创建虚拟头节点,统一处理逻辑,避免分类讨论dummy = ListNode(0)dummy.next = head# 初始化快慢指针,都指向虚拟头节点fast = slow = dummy# 第一步:快指针先走n步# 这样后面快指针到末尾时,慢指针正好在待删除节点的前一个位置for i in range(n):fast = fast.next# 第二步:快慢指针同时移动# fast.next 判断确保fast最后指向最后一个节点while fast.next:fast = fast.nextslow = slow.next# 第三步:删除倒数第n个节点# slow指向待删除节点的前一个节点slow.next = slow.next.next# 返回真实头节点return dummy.next
2.3 复杂度分析
- 时间复杂度: O ( N ) O(N) O(N),其中 N N N为链表长度
- 快指针先走 n n n步: O ( n ) O(n) O(n)
- 快慢指针同步走到末尾: O ( N − n ) O(N-n) O(N−n)
- 空间复杂度: O ( 1 ) O(1) O(1)
- 只使用了虚拟头节点: O ( 1 ) O(1) O(1)
- 快慢指针: O ( 1 ) O(1) O(1)
3 题目总结
题目难度:中等
数据结构:链表
应用算法:快慢双指针