目录
暴力破解技术
使用慢速和快速指针(单次迭代)
示例
算法
输出
首页 后端开发 Python教程 获取链表的中间元素的Python程序,在单次迭代中完成

获取链表的中间元素的Python程序,在单次迭代中完成

Sep 14, 2023 am 11:21 AM
链表 python程序 中间元素

链表用于将数据存储在不连续的内存位置。包含数据项的节点使用指针链接。每个节点由两个字段组成。第一个字段用于存储数据,第二个字段包含到下一个节点的链接。

暴力破解技术

要找到链表的中间元素,暴力破解技术是通过迭代整个链表直到遇到 NULL 为止来找出链表的长度,然后将长度除以 2 得到链表的索引中间的元素。得到中间元素的索引后,从头开始再次迭代链表,到达需要的索引时停止。该索引处的数据项给出了中间元素。

  • 取一个名为“temp”的变量指向 HEAD 并将“len”初始化为 0

  • 使用 temp 迭代链表,直到达到 NULL,并在每个节点将“len”加 1。

  • 获取链表的长度后,再次将temp初始化为HEAD。迭代链表直到len//2。

使用慢速和快速指针(单次迭代)

我们将使用两个指针来遍历链表。一种称为“慢指针”,另一种称为“快指针”。

快指针的移动速度是慢指针的两倍。

当快指针到达链表末尾时,慢指针将位于中间节点。

因此,我们可以直接打印中间节点的内容。

示例

考虑下面的链接列表。中间的元素是3。

获取链表的中间元素的Python程序,在单次迭代中完成

快指针已到达链表中的最后一个节点,现在慢指针指向节点 3。因此,3 是给定链表的中间元素。现在,考虑 6 个节点。

获取链表的中间元素的Python程序,在单次迭代中完成

示例

快指针已达到 NULL,慢指针指向第 4 个节点。因此,中间元素为 4。

算法

  • 使“慢”和“快”指向链表的HEAD。

  • 将快指针加 2,将慢指针加 1,直到快指针和 fast.next 不等于 NULL

  • 打印慢指针处的值。

  • 时间复杂度为 O(n)。

class Node:
  def __init__(self, val):
      self.val = val
      self.next = None
class LinkedList:
  def __init__(self):
      self.head = None

  def insert_at_the_beginning(self, newVal):
      newNode = Node(newVal)
      newNode.next = self.head
      self.head = newNode
  def print_middle_element(self):
      slow=self.head
      fast=self.head
      while fast is not None and fast.next is not None:
          slow=slow.next      #slow pointer moves one node
          fast=fast.next.next  #fast pointer moves two nodes
      print("\n\nthe middle element is ",slow.val)
  def Print_the_LL(self):
      temp = self.head
      if(temp != None):
        print("The linked list elements are:", end=" ")
        while (temp != None):
          print(temp.val, end=" ")
          temp = temp.next
      else:
        print("The list is empty.")
newList = LinkedList()
newList.insert_at_the_beginning(5)
newList.insert_at_the_beginning(4)
newList.insert_at_the_beginning(3)
newList.insert_at_the_beginning(2)
newList.insert_at_the_beginning(1)
newList.Print_the_LL()
newList.print_middle_element()
登录后复制

输出

The linked list elements are: 1 2 3 4 5 

the middle element is  3
登录后复制

以上是获取链表的中间元素的Python程序,在单次迭代中完成的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

notepad++怎么运行python程序 notepad++怎么运行python程序 Apr 08, 2024 am 03:24 AM

使用 Notepad++ 运行 Python 程序需要以下步骤:1. 安装 Python 插件;2. 创建 Python 文件;3. 设置运行选项;4. 运行程序。

PyCharm使用教程:详细指引你运行操作 PyCharm使用教程:详细指引你运行操作 Feb 26, 2024 pm 05:51 PM

PyCharm是一款非常流行的Python集成开发环境(IDE),它提供了丰富的功能和工具,使得Python开发变得更加高效和便捷。本文将为大家介绍PyCharm的基本操作方法,并提供具体的代码示例,帮助读者快速入门并熟练操作该工具。1.下载和安装PyCharm首先,我们需要前往PyCharm官网(https://www.jetbrains.com/pyc

PyCharm社区版支持的插件足够吗? PyCharm社区版支持的插件足够吗? Feb 20, 2024 pm 04:42 PM

PyCharm社区版支持的插件足够吗?需要具体代码示例随着Python语言在软件开发领域的应用越来越广泛,PyCharm作为一款专业的Python集成开发环境(IDE),备受开发者青睐。PyCharm分为专业版和社区版两个版本,其中社区版是免费提供的,但其插件支持相对专业版有所限制。那么问题来了,PyCharm社区版支持的插件足够吗?本文将通过具体的代码示例

PyCharm高级教程:利用PyInstaller将代码打包为EXE格式 PyCharm高级教程:利用PyInstaller将代码打包为EXE格式 Feb 20, 2024 am 09:34 AM

PyCharm是一款功能强大的Python集成开发环境,提供了丰富的功能和工具来帮助开发者提高效率。其中,PyInstaller是一个常用的工具,可以将Python代码打包为可执行文件(EXE格式),方便在没有Python环境的机器上运行。在本篇文章中,我们将介绍如何在PyCharm中使用PyInstaller将Python代码打包为EXE格式,并提供具体的

python程序的开发流程 python程序的开发流程 Apr 20, 2024 pm 09:22 PM

Python 程序开发流程包括以下步骤:需求分析:明确业务需求和项目目标。设计:确定架构和数据结构,绘制流程图或使用设计模式。编写代码:使用 Python 编程,遵循编码规范和文档注释。测试:编写单元和集成测试,进行手动测试。审查和重构:审查代码,发现缺陷和改进可读性。部署:将代码部署到目标环境中。维护:修复错误、改进功能,并监控更新。

Flask安装配置教程:轻松搭建PythonWeb应用的利器 Flask安装配置教程:轻松搭建PythonWeb应用的利器 Feb 20, 2024 pm 11:12 PM

Flask安装配置教程:轻松搭建PythonWeb应用的利器,需要具体代码示例引言:随着Python的日益流行,Web开发也成为了Python程序员的必备技能之一。而要进行Python的Web开发,我们需要选择合适的Web框架。在众多的PythonWeb框架中,Flask是一款简洁、易上手且灵活的框架,备受开发者们的青睐。本文将介绍Flask框架的安装、

Python GIL入门指南:如何理解和使用全局解释器锁 Python GIL入门指南:如何理解和使用全局解释器锁 Feb 27, 2024 am 09:10 AM

什么是GIL?GIL是全局解释器锁的缩写,它是python解释器的一个重要概念。GIL确保了Python解释器一次只能执行一个线程。这意味着在任何时候,只有一个线程可以运行Python字节码。其他线程必须等待GIL可用才能继续执行。GIL是如何工作的?GIL是一个由C语言编写的锁,它位于Python解释器中。当一个线程想要执行Python字节码时,它必须首先获取GIL。如果GIL已经被另一个线程持有,那么该线程必须等待GIL可用才能继续执行。GIL对Python程序有什么影响?GIL对Pytho

Llama3突然来袭!开源社区再次沸腾:GPT4级模型自由访问时代到来 Llama3突然来袭!开源社区再次沸腾:GPT4级模型自由访问时代到来 Apr 19, 2024 pm 12:43 PM

Llama3来了!就在刚刚,Meta官网上新,官宣了Llama380亿和700亿参数版本。并且推出即为开源SOTA:Meta官方数据显示,Llama38B和70B版本在各自参数规模上超越一众对手。8B模型在MMLU、GPQA、HumanEval等多项基准上均胜过Gemma7B和Mistral7BInstruct。而70B模型则超越了闭源的当红炸子鸡Claude3Sonnet,和谷歌的GeminiPro1.5打得有来有回。Huggingface链接一出,开源社区再次沸腾。眼尖的盲生们还第一时间发现

See all articles