資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式檢測連結串列中的環
當需要檢測連結串列中的環時，定義了一個向連結串列新增元素的方法和一個獲取連結串列中元素的方法。還定義了另一個方法，該方法檢查頭節點和尾節點的值是否相同。根據此結果，可以檢測到環。
下面是相同內容的演示 -
示例
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList_structure:
def __init__(self):
self.head = None
self.last_node = None
def add_vals(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def get_node_val(self, index):
curr = self.head
for i in range(index):
curr = curr.next
if curr is None:
return None
return curr
def check_cycle(my_list):
slow_val = my_list.head
fast_val = my_list.head
while (fast_val != None and fast_val.next != None):
slow_val = slow_val.next
fast_val = fast_val.next.next
if slow_val == fast_val:
return True
return False
my_linked_list = LinkedList_structure()
my_list = input('Enter the elements in the linked list ').split()
for elem in my_list:
my_linked_list.add_vals(int(elem))
my_len = len(my_list)
if my_len != 0:
vals = '0-' + str(my_len - 1)
last_ptr = input('Enter the index [' + vals + '] of the node' ' at which the last node has to point'' (Enter nothing to point to None): ').strip()
if last_ptr == '':
last_ptr = None
else:
last_ptr = my_linked_list.get_node_val(int(last_ptr))
my_linked_list.last_node.next = last_ptr
if check_cycle(my_linked_list):
print("The linked list has a cycle")
else:
print("The linked list doesn't have a cycle")輸出
Enter the elements in the linked list 56 78 90 12 4 Enter the index [0-4] of the node at which the last node has to point (Enter nothing to point to None): The linked list doesn't have a cycle
解釋
建立“Node”類。
建立另一個具有所需屬性的“LinkedList_structure”類。
它有一個“init”函式，用於初始化第一個元素，即“head”為“None”。
定義了一個名為“add_vals”的方法，該方法有助於向棧中新增值。
定義了另一個名為“get_node_val”的方法，該方法有助於獲取連結串列中當前節點的值。
定義了另一個名為“check_cycle”的方法，該方法有助於查詢頭節點和尾節點是否相同，這意味著這將是一個環。
它根據環的存在與否返回True或False。
建立“LinkedList_structure”的一個例項。
向連結串列中新增元素。
在此連結串列上呼叫“check_cycle”方法。
在控制檯上顯示輸出。
更新於: 2021年4月14日
374 次瀏覽
廣告