2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Posted at

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day34「118. Pascal's Triangle」

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

Twitterやってます。

問題

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のいずれかを使うと良いよ!ってなってます。
気になるかたはそちらをチェックすることもお勧めします。

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

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?