当链表中的任何节点不指向 NULL 时,就称链表存在循环。最后一个节点将指向链表中的前一个节点,从而创建一个循环。有环的链表不会有终点。
在下面的示例中,最后一个节点(节点 5)未指向 NULL。相反,它指向节点 3,并建立了一个循环。因此,上面的链表是没有尽头的。
算法快速和慢速获取两个指针
两个指针最初都会指向链表的 HEAD。
慢速指针总是加一,快指针总是加二。
在任何时候,如果快指针和慢指针都指向同一个节点,则称链表存在环。
考虑下面的链表示例,其中最后一个节点指向第二个节点 -
示例
慢指针和快指针都指向同一个节点。因此,可以得出结论,给定的链表包含一个循环。
'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