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

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

हल करने के चरण

• एक सेट लें जिसे हैश सेट H कहा जाता है
• जब तक head null नहीं है
  • यदि head H में मौजूद है, तो true वापस करें
  • head को H में जोड़ें
  • head := head का अगला
• false वापस करें

उदाहरण

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

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