Giao điểm hai danh sách liên kết trong Python

Cho hai danh sách liên kết A, B. Trả về tham chiếu đến nút giao điểm. Input: intersectionVal = 8, A = [4,1,8,4,5], B = [5,0,1,8,4,5], skipA = 2, skipB = 3.

Giải pháp

Sử dụng hash map:

• Tạo dict d.
• Duyệt headA: d[headA] = 1, headA = headA.next.
• Duyệt headB: nếu headB trong d → trả về headB; else headB = headB.next.
• Trả về null nếu không tìm thấy.

Ví dụ

Triển khai Python:

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)

Đầu vào

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))

Đầu ra

Intersected at '8'