पायथन में लिंक्ड लिस्ट साइकिल

मान लें कि हमारे पास एक लिंक्ड सूची है, और हमें यह जांचना है कि कोई चक्र है या नहीं। दी गई लिंक्ड सूची में चक्र का प्रतिनिधित्व करने के लिए, हम पॉज़ नामक एक पूर्णांक सूचक का उपयोग करेंगे। यह स्थिति लिंक की गई सूची में एक स्थिति का प्रतिनिधित्व करती है जहां पूंछ जुड़ा हुआ है। तो अगर पॉज़ -1 है, तो लिंक की गई सूची में कोई चक्र मौजूद नहीं है। उदाहरण के लिए, लिंक की गई सूची [5, 3, 2, 0, -4, 7] और pos =1 जैसी है। तो एक चक्र है, और पूंछ दूसरे नोड से जुड़ी है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक सेट को हैश सेट एच के रूप में लें
• जबकि सिर शून्य नहीं है -
  • यदि एच में सिर मौजूद है, तो सही लौटें
  • हेड को एच में जोड़ें
  • सिर:=सिर के आगे
• झूठी वापसी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class ListNode:
   def __init__(self, data, next = None):
      self.data = data
      self.next = next
def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head
def get_node(head, pos):
   if pos != -1:
      p = 0
      ptr = head
      while p < pos:
         ptr = ptr.next
         p += 1
      return ptr
class Solution(object):
   def hasCycle(self, head):
      hashS = set()
      while head:
         if head in hashS:
            return True
         hashS.add(head)
         head = head.next
      return False
head = make_list([5,3,2,0,-4,7])
last_node = get_node(head, 5)
pos = 1
last_node.next = get_node(head, pos)
ob1 = Solution()
print(ob1.hasCycle(head))

इनपुट

List = [5,3,2,0,-4,7]
Pos = 1

आउटपुट

True