Python程式檢測鍊錶中的循環

當鍊錶中的任何節點不指向 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

以上是Python程式檢測鍊錶中的循環的詳細內容。更多資訊請關注PHP中文網其他相關文章！