ゼロから始めるLeetCode Day35「160. Intersection of Two Linked Lists」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day34「118. Pascal’s Triangle」
次回
ゼロから始めるLeetCode Day36「155. Min Stack」

問題

160. Intersection of Two Linked Lists

Top 100 Liked QuestionsのEasy問題の最後から二つ目の問題です。

問題としては、2つの単方向連結リストの共通部分が始まるノードを見つけてくださいというものです。

例が図で解説されており、諸事情でこちらに直接載せることはできないので各々が確認して頂けると幸いです。

解法

最初こう書いたら、

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        
        LNA = headA
        LNB = headB
        while LNA != LNB:
            if LNA == None:
                LNA = headB
            else:
                LNA.next
            
            if LNB == None:
                LNB == headA
            else:
                LNB.next
        return LNA
# Time Limit Exceeded

時間切れになったので、以下のようにwhile以降を内包表記で書き直してみたら行けました。

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        
        LNA = headA
        LNB = headB
        while LNA != LNB:
            LNA = headB if LNA == None else LNA.next
            LNB = headA if LNB == None else LNB.next
        return LNA
# Runtime: 168 ms, faster than 75.08% of Python3 online submissions for Intersection of Two Linked Lists.
# Memory Usage: 29.1 MB, less than 100.00% of Python3 online submissions for Intersection of Two Linked Lists.

なお、この問題の公式の解説の解き方ではBruteForce,HashMap,Two Pointerのいずれかを使うと良いよ！ってなってます。
気になるかたはそちらをチェックすることもお勧めします。

こっちの書き方の方が良いよ！とかこの言語で書いてみたよ！とかがあれば是非コメントしてみてください。