ゼロから始めるLeetCode Day84「142. Linked List Cycle Ⅱ」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day83 「102. Binary Tree Level Order Traversal」

次回
ゼロから始めるLeetCode Day85 「6. ZigZag Conversion」

Twitterやってます。

問題

142. Linked List Cycle Ⅱ
難易度はMedium。
前回もそうでしたが、問題集からの抜粋です。

問題としては、以前解いたLinked List Cycleと似たような形式です。
連結リストが与えられます。その連結リストのサイクルが始まるノードを返します。仮にサイクルがない場合はnullを返します。

与えられた連結リスト内のサイクルを表現するには、連結リスト内の末尾が接続する位置（インデックス0）を表す整数posを使用します。posが-1の場合、リンク先リストにはサイクルはありません。

注意：リンク先のリストを変更しないでください。

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

解法

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        root,dic = head,{}
        while root:
            if root in dic:
                return root
            dic[root] = 1
            root = root.next
        return root
# Runtime: 56 ms, faster than 51.83% of Python3 online submissions for Linked List Cycle II.
# Memory Usage: 16.9 MB, less than 51.15% of Python3 online submissions for Linked List Cycle II.

辞書を使って管理しました。

あとで考え直してみたら二つpointerを使って解いた方が分かりやすい気がしましたがまあ今回はこれでいいかなと思います。
解き続けることが一番重要ですしね!!

では今回はここまで。お疲れ様でした。