পাইথনে লিংকড লিস্ট সাইকেল ডিটেকশন

একটি লিংকড লিস্টে সাইকেল (চক্র) আছে কিনা তা যাচাই করতে হবে। pos প্যারামিটার দিয়ে টেইল কোন নোডের সাথে কানেক্টেড তা বোঝানো হয়। pos = -1 মানে সাইকেল নেই। উদাহরণ: [5,3,2,0,-4,7], pos = 1 হলে সাইকেল আছে।

সমাধানের পদ্ধতি

1. একটি হ্যাশ সেট H নিন।
2. while head is not None:
   • যদি head H-তে থাকে, True রিটার্ন করুন।
   • head-কে H-এ যোগ করুন।
   • head = head.next।
3. 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