Giao điểm của hai danh sách được liên kết trong Python

Giả sử chúng ta có hai danh sách liên kết A và B, có ít phần tử trong các danh sách liên kết này. Chúng ta phải trả về tham chiếu của các điểm giao nhau. Các đầu vào là giao điểmVal =8, A =[4,1,8,4,5], B =[5,0,1,8,4,5], bỏ quaA =2 và bỏ quaB =3, chúng được sử dụng để bỏ qua 2 phần tử từ A và bỏ qua 3 phần tử từ B.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ được gọi là d
• trong khi headA không rỗng
  • d [headA]:=1
  • headA:=tiếp theo của headA
• trong khi headB không rỗng
  • nếu headB trong d
    • quay lại headB
  • headB:=tiếp theo của headB
• Trả về null

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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)

Đầ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'