Pythonで2つの連結リストの交差ノードを求める方法

ここでは、2つの連結リスト（リンクリスト）AとBが与えられ、それぞれにいくつかの要素が含まれている状況を考えます。このとき、両方のリストが交差しているノードへの参照を返す必要があります。

例として、次のような入力を扱います。

• intersectionVal = 8
• A = [4, 1, 8, 4, 5]
• B = [5, 0, 1, 8, 4, 5]
• skipA = 2
• skipB = 3

skipAとskipBは、それぞれリストAから2要素、リストBから3要素をスキップして交差ノードに到達することを示しています。つまり、両リストは値「8」を持つノードで合流します。

解法のアプローチ

この問題は、ハッシュマップ（辞書）を使うことで効率的に解決できます。手順は以下の通りです。

1. 空の辞書 d を定義します。
2. headA が null でない間、以下を繰り返します。
   • d[headA] := 1 としてノードを記録
   • headA := headA の次のノードへ移動
3. headB が null でない間、以下を繰り返します。
   • もし headB が d に存在すれば、headB を返す（これが交差ノード）
   • そうでなければ headB := headB の次のノードへ移動
4. 最後まで見つからなければ null を返します。

この方法では、まずリストAのすべてのノードを辞書に登録し、その後リストBを走査しながら「同じノードオブジェクト」が既に辞書に存在するかを確認します。値が同じでも別のノードオブジェクトであれば交差とはみなされない点が重要です。

計算量は時間 O(m + n)、空間 O(m)（m、nはそれぞれのリストの長さ）となります。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

class ListNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head2: ListNode
        :rtype: ListNode
        """
        d = {}
        while headA:
            d[headA] = 1
            headA = headA.next
        while headB:
            if headB in d:
                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'

この結果から、リストAとリストBは値「8」を持つノードで交差していることが確認できます。ハッシュマップによるノードの記録と照合により、交差ノードを正確に特定できるのがポイントです。