Python程序检测链表中的循环

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

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

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

• 两个指针最初都会指向链表的 HEAD。

• 慢速指针总是加一，快指针总是加二。

• 在任何时候，如果快指针和慢指针都指向同一个节点，则称链表存在环。

  立即学习“Python免费学习笔记（深入）”；

  

  Kuwebs企业网站管理系统3.1.5 UTF8

  酷纬企业网站管理系统Kuwebs是酷纬信息开发的为企业网站提供解决方案而开发的营销型网站系统。在线留言模块、常见问题模块、友情链接模块。前台采用DIV+CSS，遵循SEO标准。 1.支持中文、英文两种版本，后台可以在不同的环境下编辑中英文。 3.程序和界面分离，提供通用的PHP标准语法字段供前台调用，可以为不同的页面设置不同的风格。 5.支持google地图生成、自定义标题、自定义关键词、自定义描

  下载

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

示例

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

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


class 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("\nThe 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("\nA loop has been detected in the linked list ")
                return
            slow=slow.next
            fast=fast.next


newList = 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("\n")
newList.head.next.next.next.next=newList.head.next
newList.detect_loop()

输出

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

The linked list elements are: 1 2 3 4 

A loop has been detected in the linked list