鏈表是一種數據結構,它由一個個節點組成。每個節點包含兩個部分,一個是數據部分,一個是指向下一個節點的指針。鏈表帶環則是在鏈表中設置了一個環路,使得鏈表的尾部與其中的某個節點形成了一個環,這樣就使得鏈表的遍歷變得更加復雜。
class Node: def __init__(self, value): self.value = value self.next = None class Linked_List: def __init__(self): self.head = None # 添加新的節點 def add_node(self, value): if not self.head: self.head = Node(value) else: current_node = self.head while current_node.next: current_node = current_node.next current_node.next = Node(value) # 創建一個帶環的鏈表 def create_cycle(self, pos): if not self.head: return current_node = self.head i = 0 while i< pos: current_node = current_node.next i += 1 cycle = current_node while current_node.next: current_node = current_node.next current_node.next = cycle # 判斷鏈表是否帶環 def has_cycle(self): slow, fast = self.head, self.head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False # 創建一個鏈表 linked_list = Linked_List() linked_list.add_node(1) linked_list.add_node(2) linked_list.add_node(3) linked_list.add_node(4) linked_list.add_node(5) linked_list.add_node(6) # 創建一個帶環的鏈表 linked_list.create_cycle(3) print(linked_list.has_cycle()) # True
上面的代碼中,我們定義了一個鏈表類 Linked_List 和一個節點類 Node 。鏈表類中包含三個方法,add_node 方法用于添加新的節點,create_cycle 方法用于創建一個帶環的鏈表,has_cycle 方法用于判斷鏈表是否帶環。
在 create_cycle 方法中,我們首先找到指定位置的節點作為環的起點,然后從這個節點開始遍歷鏈表,找到鏈表的尾部,將它的下一個節點指向環的起點,這樣就形成了一個帶環的鏈表。
在 has_cycle 方法中,我們使用兩個指針 slow 和 fast ,開始時它們都指向鏈表的頭部,slow 每次移動一個節點,fast 每次移動兩個節點。如果鏈表帶環,那么 fast 最終會追上 slow ,此時就說明鏈表帶環。