สมมติว่าเรามีรายการเชื่อมโยง 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
- ในขณะที่ headA ไม่เป็นโมฆะ
- d[headA] :=1
- headA :=ถัดจาก headA
- ในขณะที่ headB ไม่เป็นค่าว่าง
- ถ้า headB ใน d
- กลับหัวB
- headB :=ถัดจาก headB
- ถ้า headB ใน d
- คืนค่า 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'
