数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序获取单次迭代链表的中间元素
链表用于存储非连续内存位置中的数据。包含数据项的节点使用指针链接。每个节点包含两个字段。第一个字段用于存储数据，第二个字段包含指向下一个节点的链接。
暴力破解技术
为了找到链表的中间元素，暴力破解技术是通过迭代整个链表直到遇到 NULL 来找出链表的长度，然后将长度除以 2 以获取中间元素的索引。获取中间元素的索引后，再次从头部迭代链表，并在到达所需索引时停止。该索引处的数据项给出中间元素。
取一个名为“temp”的变量指向 HEAD 并将“len”初始化为 0
使用 temp 迭代链表，直到到达 NULL 并对每个节点将“len”递增 1。
获取链表的长度后，再次将 temp 初始化为 HEAD。迭代链表直到 len//2。
使用慢速和快速指针（单次迭代）
我们将使用两个指针遍历链表。一个称为“慢速指针”，另一个称为“快速指针”。
快速指针将以慢速指针的两倍速度移动。
当快速指针到达链表的末尾时，慢速指针将位于中间节点。
因此，我们可以直接打印中间节点的内容。
示例
考虑以下链表。中间元素是 3。
快速指针已到达链表的最后一个节点，现在慢速指针指向节点 3。因此，3 是给定链表的中间元素。现在，考虑 6 个节点。
示例
快速指针已到达 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
更新于: 2023年4月24日
1K+ 浏览量
广告