जब किसी लिंक की गई सूची में एक चक्र का पता लगाने की आवश्यकता होती है, तो लिंक की गई सूची में तत्वों को जोड़ने की एक विधि और लिंक की गई सूची में तत्व प्राप्त करने की एक विधि परिभाषित की जाती है। एक और तरीका परिभाषित किया गया है जो जांचता है कि सिर और पीछे के मान समान हैं या नहीं। इस परिणाम के आधार पर, चक्रों का पता लगाया जाता है।
नीचे उसी के लिए एक प्रदर्शन है -
उदाहरण
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
स्पष्टीकरण
-
'नोड' वर्ग बनाया गया है।
-
आवश्यक विशेषताओं के साथ एक और 'लिंक्डलिस्ट_स्ट्रक्चर' वर्ग बनाया गया है।
-
इसमें एक 'init' फंक्शन होता है जिसका इस्तेमाल पहले एलिमेंट यानी 'हेड' से 'कोई नहीं' को इनिशियलाइज़ करने के लिए किया जाता है।
-
'add_vals' नाम की एक विधि परिभाषित की गई है, जो स्टैक में मान जोड़ने में मदद करती है।
-
'get_node_val' नाम की एक अन्य विधि परिभाषित की गई है, जो लिंक की गई सूची में वर्तमान नोड का मान प्राप्त करने में मदद करती है।
-
'चेक_साइकिल' नामक एक अन्य विधि को परिभाषित किया गया है, जो यह पता लगाने में मदद करती है कि क्या सिर और पिछला भाग समान हैं, जिसका अर्थ है कि यह एक चक्र होगा।
-
यह चक्र की उपस्थिति या अनुपस्थिति के आधार पर सही या गलत लौटाता है।
-
'LinkedList_struct' का एक उदाहरण बनाया गया है।
-
लिंक की गई सूची में तत्व जोड़े जाते हैं।
-
इस लिंक की गई सूची पर 'चेक_साइकिल' विधि को कॉल किया जाता है।
-
आउटपुट कंसोल पर प्रदर्शित होता है।