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

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

हल करने के चरण

• d नामक एक मैप परिभाषित करें
• जब तक headA null नहीं है
  • d[headA] := 1
  • headA := headA का अगला
• जब तक headB null नहीं है
  • यदि headB d में है
    • headB वापस करें
  • headB := headB का अगला
• Null वापस करें

उदाहरण

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

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'