【力扣算法17】之 19. 删除链表的倒数第 N 个结点 python

简介: 【力扣算法17】之 19. 删除链表的倒数第 N 个结点 python

问题描述

给你一个链表,删除链表的倒数第 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

思路分析

  1. 首先,我们需要删除链表的倒数第n个节点。为了能够找到要删除的节点,我们需要知道链表的长度。
  2. 我们可以通过遍历链表来获取链表的长度。假设链表的长度为length
  3. 然后,我们可以根据链表的长度和要删除的节点的位置,计算出要删除的节点在正向遍历中的位置。假设要删除的节点在正向遍历中的位置为pos
  4. 接下来,我们需要找到要删除的节点的前一个节点,即倒数第n+1个节点。根据第3步计算的位置,我们可以通过遍历链表来定位到该节点。
  5. 最后,将要删除的节点从链表中移除,即将前一个节点的next指针指向下一个节点。

这个思路的关键点是使用双指针的技巧。通过快指针先向前移动n步,可以使得快指针和慢指针之间相差n个节点。然后同时移动快指针和慢指针,直到快指针到达链表的末尾。这样,慢指针所指向的节点就是要删除的节点的前一个节点。

通过这种方法,我们可以在一次遍历中找到要删除的节点的前一个节点,并进行删除操作,而不需要遍历两次链表来实现。


代码分析

  1. 创建一个虚拟头结点 dummy,并将它指向原链表的头结点 head
  2. 定义两个指针 fastslow,初始时都指向虚拟头结点。
  3. 快指针 fast 先向前移动 n 步,即 for i in range(n+1): fast = fast.next
  4. 同时移动快指针和慢指针,直到快指针 fast 到达链表的末尾。使用循环 while fast:,循环内部的操作为 fast = fast.nextslow = slow.next
  5. 此时,慢指针 slow 所指向的节点就是要删除的节点的前一个节点。
  6. 将慢指针 slow 所指向的节点的 next 指针指向下一个节点的 next 指针,即 slow.next = slow.next.next,实现删除倒数第 n 个节点。
  7. 返回 dummy.next,即为新链表的头结点。

完整代码

class Solution(object):
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)  # 创建一个虚拟头结点,值为0
        dummy.next = head  # 将虚拟头结点指向原链表的头结点
        fast = dummy  # 快指针初始指向虚拟头结点
        slow = dummy  # 慢指针初始指向虚拟头结点
        for i in range(n+1):  # 快指针先向前移动n步(包括虚拟头结点)
            fast = fast.next
        while fast:  # 同时移动快指针和慢指针,直到快指针到达链表末尾
            fast = fast.next  # 快指针每次移动一步
            slow = slow.next  # 慢指针每次移动一步
        slow.next = slow.next.next  # 删除倒数第n个节点,将慢指针指向的节点的next指针指向下一个节点的next指针
        return dummy.next  # 返回链表的头结点

详细分析


class Solution(object):
• 1

定义一个名为Solution的类。

def removeNthFromEnd(self, head, n):
• 1

定义了一个名为removeNthFromEnd的方法,该方法接受两个参数:head表示链表的头结点,n表示要删除的倒数第n个节点。

dummy = ListNode(0)
• 1

创建一个名为dummy的虚拟头结点,值为0。

dummy.next = head
• 1

将虚拟头结点的next指针指向原链表的头结点,以便建立虚拟头结点与原链表的连接。

fast = dummy
        slow = dummy

初始化快指针fast和慢指针slow,都指向虚拟头结点。

for i in range(n+1):
            fast = fast.next

快指针先向前移动n步(包括虚拟头结点),以建立快慢指针之间的n个节点的距离。

while fast:
            fast = fast.next
            slow = slow.next

同时移动快指针和慢指针,快指针每次向前移动一步,慢指针每次向前移动一步,直到快指针到达链表末尾。

slow.next = slow.next.next
• 1

删除倒数第n个节点,即将慢指针指向的节点的next指针指向下一个节点的next指针。通过跳过要删除的节点实现删除操作。

return dummy.next
• 1

返回链表的头结点,即虚拟头结点的下一个节点,用于处理删除头结点的情况。


运行效果截图


完结

相关文章
|
1月前
|
机器学习/深度学习 存储 算法
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
|
2月前
|
监控 算法 安全
深度洞察内网监控电脑:基于Python的流量分析算法
在当今数字化环境中,内网监控电脑作为“守城卫士”,通过流量分析算法确保内网安全、稳定运行。基于Python的流量分析算法,利用`scapy`等工具捕获和解析数据包,提取关键信息,区分正常与异常流量。结合机器学习和可视化技术,进一步提升内网监控的精准性和效率,助力企业防范潜在威胁,保障业务顺畅。本文深入探讨了Python在内网监控中的应用,展示了其实战代码及未来发展方向。
|
17天前
|
存储 Python
Python 实现单向链表,和单向链表的反转
链表是一种数据结构,每个节点存储相邻节点的位置信息。单链表中的节点仅存储下一节点的位置。通过Python实现单链表,定义`ListNode`类并关联节点可创建链表。例如,创建A-&gt;B-&gt;C的链表后,可通过反转函数`reverse`将链表反转为CBA。代码展示了如何实现和操作单链表。
Python 实现单向链表,和单向链表的反转
|
4天前
|
存储 算法 文件存储
探秘文件共享服务之哈希表助力 Python 算法实现
在数字化时代,文件共享服务不可或缺。哈希表(散列表)通过键值对存储数据,利用哈希函数将键映射到特定位置,极大提升文件上传、下载和搜索效率。例如,在大型文件共享平台中,文件名等信息作为键,物理地址作为值存入哈希表,用户检索时快速定位文件,减少遍历时间。此外,哈希表还用于文件一致性校验,确保传输文件未被篡改。以Python代码示例展示基于哈希表的文件索引实现,模拟文件共享服务的文件索引构建与检索功能。哈希表及其分布式变体如一致性哈希算法,保障文件均匀分布和负载均衡,持续优化文件共享服务性能。
|
9天前
|
监控 算法 安全
公司电脑网络监控场景下 Python 广度优先搜索算法的深度剖析
在数字化办公时代,公司电脑网络监控至关重要。广度优先搜索(BFS)算法在构建网络拓扑、检测安全威胁和优化资源分配方面发挥重要作用。通过Python代码示例展示其应用流程,助力企业提升网络安全与效率。未来,更多创新算法将融入该领域,保障企业数字化发展。
35 10
|
10天前
|
监控 算法 安全
基于 Python 广度优先搜索算法的监控局域网电脑研究
随着局域网规模扩大,企业对高效监控计算机的需求增加。广度优先搜索(BFS)算法凭借其层次化遍历特性,在Python中可用于实现局域网内的计算机设备信息收集、网络连接状态监测及安全漏洞扫描,确保网络安全与稳定运行。通过合理选择数据结构与算法,BFS显著提升了监控效能,助力企业实现智能化的网络管理。
26 7
|
26天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
49 12
|
25天前
|
算法 安全 网络安全
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
50 9
|
1月前
|
监控 算法 安全
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
43 10
|
2月前
|
存储 算法 安全
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
62 17

热门文章

最新文章