पायथन में दो लिंक्ड सूचियों का प्रतिच्छेदन

मान लीजिए कि हमारे पास दो लिंक्ड सूचियाँ A और B हैं, इन लिंक्ड सूचियों में कुछ तत्व हैं। हमें चौराहे के बिंदुओं का संदर्भ वापस करना होगा। इनपुट चौराहेवैल =8, ए =[4,1,8,4,5], बी =[5,0,1,8,4,5], स्किपए =2 और स्किपबी =3 हैं, इनका उपयोग स्किप करने के लिए किया जाता है A से 2 तत्व और B से 3 तत्व छोड़ें.

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

• डी नामक मानचित्र को परिभाषित करें
• जबकि शीर्षा रिक्त नहीं है
  • d[headA] :=1
  • सिरए:=सिर के आगेए
• जबकि headB रिक्त नहीं है
  • अगर हेडबी इन डी
    • रिटर्न हेडबी
  • सिर बी :=सिर के आगेबी
• वापसी शून्य

उदाहरण

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

class ListNode:
   def __init__(self, data, next = None):
      self.data = data
      self.next = next
class Solution(object):
   def getIntersectionNode(self, headA, headB):
      """
      :type head1, head1: ListNode
      :rtype: ListNode
      """
      dict = {}
      while headA:
         dict[headA]=1
         headA = headA.next
      while headB:
         if headB in dict:
            return headB
         headB = headB.next
      return None
headA = ListNode(4)
headB = ListNode(5)
Intersect = ListNode(8, ListNode(4, ListNode(5)))
headA.next = ListNode(1, Intersect)
headB.next = ListNode(0, ListNode(1, Intersect))
ob1 = Solution()
op = ob1.getIntersectionNode(headA, headB)
print("Intersection:",op.data)

इनपुट

headA = ListNode(4)
headB = ListNode(5)
Intersect = ListNode(8, ListNode(4, ListNode(5)))
headA.next = ListNode(1, Intersect)
headB.next = ListNode(0, ListNode(1, Intersect))

आउटपुट

Intersected at '8'