LeetCode / Intersection of Two Linked Lists

（ブログ記事からの転載）

[https://leetcode.com/problems/intersection-of-two-linked-lists/]

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

これもとんち的問題。2つのLinked Listが交わるnodeを返します。
ポイントはNotesのYour code should preferably run in O(n) time and use only O(1) memory.に尽きます。余計な空間計算量は使わずに解を出す必要があります。

解答・解説

解法1

私のsubmitしたコード。計算量オーダーについて条件は満たしていますが、かなり冗長になっています。

2つのポインタを2つのLinked Listの始点から動かし、終点まで移動させます。
このとき先に到着するポインタと後に到着するポインタの移動距離の差をとっておきます。
再度、2つのポインタをLinked Listの始点から動かしますが、このときは後に到着したポインタをさきほどとっておいた差の分だけ先に進めておいてから、2つのポインタをスタートさせます。
そうすると、交わる点があればポインタは必ず出会いますし、逆にポインタが出会わなければ交わる点はない、ということになります。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pa = headA
        pb = headB
        diff = 0
        if headA is headB: return headA
        while pa and pb:
            pa = pa.next
            pb = pb.next
        if not pa:
            while pb:
                pb = pb.next
                diff += 1
            while diff > 0:
                headB = headB.next
                diff -= 1
        else:
            while pa:
                pa = pa.next
                diff += 1
            while diff > 0:
                headA = headA.next
                diff -= 1
        while headA and headB:
            if headA is headB: return headA
            headA = headA.next
            headB = headB.next
        return None

解法2

よりスッキリしたコードがこちら。
2つのポインタを2つのLinked Listの始点から動かし、終点まで移動させるのは同じですが、終点に到達したら、もう一方のLinked Listの始点に移動してさらに動いていくのがミソです。
このようにすると、headA is headBとなった地点を返してやれば、交差するnodeがあればそのnodeが返りますし、交差するnodeがなければnullが返ります。
なるほどですね。。。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is None or headB is None:
            return None
        pa = headA
        pb = headB
        while pa is not pb:
            pa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.next
        return pa