当前位置: 首页 > news >正文

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 1sz30
  • 0 ≤ N o d e . v a l ≤ 100 0 \leq Node.val \leq 100 0Node.val100
  • 1 ≤ n ≤ s z 1 \leq n \leq sz 1nsz

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(Nn)
  • 空间复杂度: O ( 1 ) O(1) O(1)
    • 只使用了虚拟头节点: O ( 1 ) O(1) O(1)
    • 快慢指针: O ( 1 ) O(1) O(1)

3 题目总结

题目难度:中等
数据结构:链表
应用算法:快慢双指针


http://www.mrgr.cn/news/71936.html

相关文章:

  • Java开发人员从零学习ArkTs笔记(二)-函数与类
  • ABAP开发学习——权限控制
  • STM32(hal库)在串口中,USART和uart有什么区别?
  • pycharm报错:no module named cv2.cv2
  • 常用字符串和集合处理工具类
  • SSE (Server-Sent Events) 服务器实时推送详解
  • 论文3—《基于YOLOv5s的农田垃圾轻量化检测方法》文献阅读分析报告
  • 我是如何一步步学习深度学习模型PyThorch
  • 信息收集系列(二):ASN分析及域名收集
  • LLM - 使用 LLaMA-Factory 微调大模型 Qwen2-VL SFT(LoRA) 图像数据集 教程 (2)
  • Python 正则表达式使用指南
  • WSL与Ubuntu系统--使用Linux
  • 渗透测试---网络基础之HTTP协议与内外网划分
  • 实战指南:理解 ThreadLocal 原理并用于Java 多线程上下文管理
  • Ngxin隐藏服务名称和版本号(源码部署和Docker部署)
  • 【最少刷题数——二分】
  • Java Review - 线程池原理源码解析
  • Ubuntu linux 命令总结
  • 如何理解DDoS安全防护在企业安全防护中的作用
  • 聊聊Flink:Flink的运行时架构
  • 几何合理的分片段感知的3D分子生成 FragGen - 评测
  • WebStorm 如何调试 Vue 项目
  • C++基础(12.红黑树实现)
  • [运维][Nginx]Nginx学习(2/5)-Nginx高级
  • 241112
  • 【Linux】————信号