Pythonでの2つのリンクリストの交差

2つのリンクリストAとBがあるとすると、これらのリンクリストにはいくつかの要素があります。交点の参照を返す必要があります。入力はintersectionVal=8、A =[4,1,8,4,5]、B =[5,0,1,8,4,5]、skipA =2、skipB =3で、これらはスキップするために使用されますAから2つの要素、Bから3つの要素をスキップします。

これを解決するには、次の手順に従います-

• dというマップを定義する
• headAがnullではない場合
  • d [headA]：=1
  • headA：=headAの次
• headBがnullではない場合
  • dのheadBの場合
    • ヘッドBを返す
  • headB：=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'