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

আমাদের একটি লিঙ্ক তালিকা আছে বিবেচনা করুন, এবং আমাদের কোন চক্র আছে কি না তা পরীক্ষা করতে হবে। প্রদত্ত লিঙ্কযুক্ত তালিকায় চক্রের প্রতিনিধিত্ব করতে, আমরা pos নামক একটি পূর্ণসংখ্যা পয়েন্টার ব্যবহার করব। এই pos লিঙ্ক করা তালিকার একটি অবস্থানের প্রতিনিধিত্ব করে যেখানে লেজ সংযুক্ত থাকে। তাই যদি pos হয় -1, তাহলে লিঙ্ক করা তালিকায় কোন চক্র উপস্থিত নেই। উদাহরণস্বরূপ, লিঙ্ক করা তালিকা হল [5, 3, 2, 0, -4, 7], এবং pos =1। তাই একটি চক্র আছে, এবং টেলটি দ্বিতীয় নোডের সাথে সংযুক্ত।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• হ্যাশ সেট H হিসাবে একটি সেট নিন
• যখন মাথা শূন্য নয় −
  • যদি হেড H তে থাকে, তাহলে true রিটার্ন করুন
  • H এ মাথা যোগ করুন
  • মাথা :=মাথার পাশে
• মিথ্যে ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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