力扣题目 19:删除链表的倒数第N个节点 【python】

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:

码上找工作icon-default.png?t=N7T8http://t.csdnimg.cn/Q59WX
作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明

给定的 n 保证是有效的。

进阶

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

解题思路

解决这个问题的关键是找到倒数第 n+1 个节点。我们可以使用两个指针 firstsecond 同时对链表进行遍历,并且 firstsecond 超前 n+1 步。当 first 遍历到链表末尾时,second 将指向倒数第 n+1 个节点。然后我们就可以调整 secondnext 指针来删除倒数第 n 个节点。

代码实现

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    
    # 移动 first,使得 first 和 second 之间相隔 n+1 个节点
    for _ in range(n + 1):
        first = first.next
    
    # 同时移动 first 和 second,直到 first 指向链表末尾
    while first is not None:
        first = first.next
        second = second.next
    
    # 删除倒数第 n 个节点
    second.next = second.next.next
    
    return dummy.next

算法分析

  • 时间复杂度:O(L),其中 L 是链表的长度。算法对链表进行了一次遍历。
  • 空间复杂度:O(1),只用了常数级别的额外空间。

算法图解

初始状态

  • 假设链表为 1 -> 2 -> 3 -> 4 -> 5n = 2,目标是删除倒数第二个节点,即节点 4
  • 我们引入一个哑节点(dummy node)作为链表的新头节点,这样可以方便地处理边界情况,比如删除头节点。

表示链表的表格如下:

添加双指针

  • 设置两个指针 firstsecond,初始时都指向哑节点。

移动 first 指针

  • first 指针向前移动 n + 1 步,使得 firstsecond 之间相隔 n 个节点。

同时移动 firstsecond 指针

  • 同时移动 firstsecond 指针,直到 first 指向链表末尾的空节点。此时,second 将指向倒数第 n + 1 个节点。

删除倒数第 N 个节点

  • 调整 secondnext 指针,使其指向倒数第 n 个节点的下一个节点,从而删除倒数第 n 个节点。

结果

删除节点 4 后的链表为:1 -> 2 -> 3 -> 5

通过这种方法,我们只需要一趟扫描就能找到倒数第 n 个节点的位置,并进行删除操作,达到高效解决问题的目的。

结论

通过使用双指针的方法,我们可以高效地解决删除链表倒数第 N 个节点的问题,这个技巧在链表问题中非常实用,值得掌握。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/538224.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Qt-绘制多边形、椭圆、多条直线

1、说明 所有的绘图操作是在绘图事件中进行。mainwindow.h #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow>QT_BEGIN_NAMESPACE namespace Ui { class MainWindow; } QT_END_NAMESPACEclass MainWindow : public QMainWindow {Q_OBJECTpublic:MainWi…

C++ 类和对象(一)

目录 0.前言 1.面向过程&面向对象 1.1面向过程编程&#xff08;PP&#xff09; 1.2面向对象编程&#xff08;OOP&#xff09; 1.3从C到C 2.类的引入 2.1C语言中的结构体 2.2C中类的引入 2.3结构体与类的区别 2.4为什么引入类 3.类的定义 3.1声明与定义不分离 …

【Java探索之旅】从输入输出到猜数字游戏

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Java编程秘籍 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一、输入输出1.1 输出到控制台1.2 从键盘输入 二、猜数字游戏2.1 所需知识&#xff1a…

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II 解法 ---------------&#x1f388;&#x1f388;题目链接&#x1f388;&#x1f388;------------------- 解法 &#x1f612;: 我的代码实现> 动规五部曲 ✒️确定dp数组以及下标的含义 dp[j]表示容量为…

Learn SRP 01

学习链接&#xff1a;Custom Render Pipeline (catlikecoding.com) 使用Unity版本&#xff1a;Unity 2022.3.5f1 1.A new Render Pipeline 1.1Project Setup 创建一个默认的3D项目&#xff0c;项目打开后可以到默认的包管理器删掉所有不需要的包&#xff0c;我们只使用Unit…

陆面、生态、水文模拟与多源遥感数据同化

原文链接&#xff1a;陆面、生态、水文模拟与多源遥感数据同化https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247601198&idx6&sn51b9b26b75c9df1f11dcb9a187878261&chksmfa820dc9cdf584df9ac3b997c767d63fef263d79d30238a6523db94f68aec621e1f91df85f6…

算法——字符串

T04BF &#x1f44b;热门专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 小比特 大梦想 此篇文章与大家分享字符串相关算法 如果有不足的或者错误的请您指出! 目录 1.最长公共前缀1.1解析1.2题解 2.最长回文子串2.1解析2.2题解 3.二级制求和3.1解析3.2题解 4.字符串相乘4.1解析4.2…

【环境变量】常见的环境变量 | 相关指令 | 环境变量系统程序的结合理解 | 环境变量表 | 本地变量环境变量 | 外部命令内建命令

目录 常见的环境变量 HOME PWD SHELL HISTSIZE 环境变量相关的指令 echo&env export unset 本地变量 环境变量整体理解 程序现象_代码查看环境变量 ​整体理解 环境变量表 环境变量表的传递 环境变量表的查看 内建命令 少说废话&#x1f197; 每个用…

大型网站系统架构演化

大型网站质量属性优先级&#xff1a;高性能 高可用 可维护 应变 安全 一、单体架构 应用程序&#xff0c;数据库&#xff0c;文件等所有资源都在一台服务器上。 二、垂直架构 应用和数据分离&#xff0c;使用三台服务器&#xff1a;应用服务器、文件服务器、数据服务器 应用服…

JavaEE 初阶篇-深入了解 CAS 机制与12种锁的特征(如乐观锁和悲观锁、轻量级锁与重量级锁、自旋锁与挂起等待锁、可重入锁与不可重入锁等等)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 乐观锁与悲观锁概述 1.1 悲观锁&#xff08;Pessimistic Locking&#xff09; 1.2 乐观锁&#xff08;Optimistic Locking&#xff09; 1.3 区别与适用场景 2.0 轻…

我企业的业务需要制作企业网站吗?11个支持的理由以及5个反对的理由!

如果你的企业经营得还不错&#xff0c;你可能会找出很多理由&#xff0c;说明为什么一个高效的网站对你来说并不那么重要。确实&#xff0c;你明白企业需要在互联网上有一定的存在感&#xff0c;但你可能并不认为一个高效的网站会对你的特定业务产生太大的影响——尤其是当你已…

实战纪实 | 编辑器漏洞之Ueditor-任意文件上传漏洞 (老洞新谈)

UEditor 任意文件上传漏洞 前言 前段时间在做某政府单位的项目的时候发现存在该漏洞&#xff0c;虽然是一个老洞&#xff0c;但这也是容易被忽视&#xff0c;且能快速拿到shell的漏洞&#xff0c;在利用方式上有一些不一样的心得&#xff0c;希望能帮助到一些还不太了解的小伙…

PCIe总线-存储器域和PCIe总线域访问流程(二)

1.概述 PCIe总线的最大特点是像CPU访问DDR一样&#xff0c;可以直接使用地址访问PCIe设备&#xff08;桥&#xff09;&#xff0c;但不同的是DDR和CPU同属于存储器域&#xff0c;而CPU和PCIe设备属于两个不同的域&#xff0c;PCIe设备&#xff08;桥&#xff09;的地址空间属于…

[RK3399 Linux] 使用busybox 1.36.1制作rootfs

一、 编译、安装、配置 busybox 1.1 下载源码 根文件系统是根据busybox来制作的。 下载地址:https://busybox.net/downloads/。 这里就以1.36.1版本为例进行编译安装介绍: 注意:编译linux内核与文件系统中的所有程序要使用相同的交叉编译器。 下载完成后解压: mkdir …

03 SQL基础 -- 查询与运算符

一、SELECT 语句基础 1.1 从表中选取数据 SELECT 语句 从表中选取数据时需要使用SELECT语句,也就是只从表中选出(SELECT)必要数据的意思。通过SELECT语句查询并选取出必要数据的过程称为匹配查询或查询(query) 基本SELECT语句包含了SELECT和FROM两个子句(clause)。示…

NAT实验

要求&#xff1a; 1、AR2为ISP路由器&#xff0c;其上只能配置IP地址&#xff0c;不得再进行其他的任何配置 2、PC1-PC2可以ping通客户平板和DNS服务器&#xff1b; 3、客户端可以通过域名访问http1&#xff0c;通过地址访问http2 4、R1为边界路由器&#xff0c;其上只有一…

计算机视觉工程师

为进一步贯彻落实中共中央印发《关于深化人才发展体制机制改革的意见》和国务院印发《关于“十四五”数字经济发展规划》等有关工作的部署要求&#xff0c;深入实施人才强国战略和创新驱动发展战略&#xff0c;加强全国数字化人才队伍建设&#xff0c;持续推进人工智能从业人员…

【深度学习】深度学习md笔记总结第4篇:TensorFlow介绍,学习目标【附代码文档】

深度学习笔记完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;深度学习课程&#xff0c;深度学习介绍要求,目标,学习目标,1.1.1 区别,学习目标,学习目标。TensorFlow介绍&#xff0c;2.4 张量学习目标,2.4.1 张量(Tensor),2.4.2 创建张量的指令,2.4.3 张量…

C语言世界上最详细自定义类型:联合和枚举

前言&#xff1a; hello! 大家好&#xff0c;我是小陈&#xff0c;今天给大家带来一篇联合和枚举的博客&#xff01;&#xff01;&#xff01; 1.联合体类型的声明 像结构体⼀样&#xff0c;联合体也是由⼀个或者多个成员构成&#xff0c;这些成员可以不同的类型。 但是编译…

安装达梦(DM8)数据库(图形化安装)

一、配置DM8数据库系统环境 在CentOS7系统环境安装DM8&#xff08;达梦&#xff09;数据库前的准备。&#xff08;注意&#xff1a;安装前必须创建 dmdba 用户&#xff0c;禁止使用 root 用户安装数据库。&#xff09; 1、新建用户 运行SecureCRT工具&#xff0c;root登录16…