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

দুটি লিংকড লিস্ট A এবং B দেওয়া থাকে। তাদের ইন্টারসেকশন পয়েন্ট (কমন নোড) বের করতে হবে। ইনপুট হিসেবে intersectionVal = 8, A = [4,1,8,4,5], B = [5,0,1,8,4,5], skipA = 2, skipB = 3 দেওয়া থাকে।

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

1. একটি হ্যাশ ম্যাপ d তৈরি করুন।
2. headA ট্রাভার্স করে সব নোড d-এ রাখুন।
3. headB ট্রাভার্স করুন: যদি কোনো নোড d-এ পাওয়া যায়, সেটিই ইন্টারসেকশন পয়েন্ট।
4. নहीं পেলে None রিটার্ন করুন।

উদাহরণ কোড

class ListNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        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'