Python程序检测链表中的循环

百变鹏仔 3小时前 #Python

文章标签链表

当链表中的任何节点不指向 null 时，就称链表存在循环。最后一个节点将指向链表中的前一个节点，从而创建一个循环。有环的链表不会有终点。

在下面的示例中，最后一个节点（节点 5）未指向 NULL。相反，它指向节点 3，并建立了一个循环。因此，上面的链表是没有尽头的。

算法快速和慢速获取两个指针

两个指针最初都会指向链表的 HEAD。
慢速指针总是加一，快指针总是加二。
在任何时候，如果快指针和慢指针都指向同一个节点，则称链表存在环。
立即学习“Python免费学习笔记（深入）”；

考虑下面的链表示例，其中最后一个节点指向第二个节点 -

示例

慢指针和快指针都指向同一个节点。因此，可以得出结论，给定的链表包含一个循环。

class Node:    def __init__(self, val):        self.val = val        self.next = Noneclass LinkedList:    def __init__(self):        self.head = None    def insert_at_the_end(self,newVal):        newNode=Node(newVal)        if self.head==None:            self.head=newNode            return        temp=self.head        while(temp.next):            temp=temp.next        temp.next=newNode    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.")    def detect_loop(self):        slow=self.head        fast=self.head        while(fast):            if slow==fast:                print("A loop has been detected in the linked list ")                return            slow=slow.next            fast=fast.nextnewList = LinkedList()newList.insert_at_the_end(1)newList.insert_at_the_end(2)newList.insert_at_the_end(3)newList.insert_at_the_end(4)newList.Print_the_LL()print("")newList.head.next.next.next.next=newList.head.nextnewList.detect_loop()

输出

在链表中检测到了一个循环。

The linked list elements are: 1 2 3 4 A loop has been detected in the linked list

文章推荐

Python程序检测链表中的循环

算法快速和慢速获取两个指针

示例

输出

Python中使用Beautiful Soup进行网页抓取：基础知识探究

使用Python计算神经机器翻译的BLEU分数

探索 Python 包的使用

使用Python获取文件中的字符数、单词数、空格数和行数

封装在Python中是什么？