จุดตัดของลิงค์ลิสต์สองตัวใน Python

สมมติว่าเรามีลิงค์ลิสต์สองตัวคือ A และ B มีองค์ประกอบอยู่บ้าง เราต้องคืนค่าอ้างอิงของจุดตัด จุดตัดมีค่า intersectionVal = 8, A = [4,1,8,4,5], B = [5,0,1,8,4,5], skipA = 2 และ skipB = 3 ใช้เพื่อข้าม 2 องค์ประกอบจาก A และข้าม 3 องค์ประกอบจาก B

วิธีการแก้ปัญหา

• กำหนดแมพชื่อ d
• while headA ไม่ใช่ null:
  • d[headA] := 1
  • headA := next ของ headA
• while headB ไม่ใช่ null:
  • ถ้า headB อยู่ใน d:
    • คืนค่า headB
  • headB := next ของ 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'