ゼロから始めるLeetCode Day22「141. Linked List Cycle」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day21 「448. Find All Numbers Disappeared in an Array」
次回
ゼロから始めるLeetCode Day23「226. Invert Binary Tree」

問題

141. Linked List Cycle

難易度はeasy。
Top 100 Liked Questionsからの抜粋です。

連結リストについての基本的な知識を求められるような問題です。

連結リストが与えられ、その中に循環があるかどうかを判断します。

指定された連結リストの循環を表すために、末尾が接続する連結リストの位置（0から始まる）を表す整数posを使用します。なお、posが-1の場合は循環がないものとします。

Example1

Input: head = [3,2,0,-4], pos = 1
Output: true
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: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

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

解法

珍しくSolutionがあったのでそこに書かれているHashTable,もといHashMapの考え方を元に実装してみました。

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        hashmap = {}
        while head != None:
            if head in hashmap:
                return True
            hashmap[head] = head
            head = head.next
        return False
# Runtime: 80 ms, faster than 9.62% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.

headの要素が空になるまでひたすらheadの要素を用意したhashmapに代入し、その次の要素をheadに代入するというものです。
仮にheadの要素がhashmapの中にあるのであればそれは循環するポイントがあるということなのでTrueを返し、最後までチェックしても存在しない場合はFalseを返す、というものです。

もう一つSolutionにあったTwoPointersというのも参考にして書いてみました。

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        pre,cur = head,head.next
        while pre != cur:
            if not cur or not cur.next:
                return False
            pre,cur = pre.next,cur.next.next
        return True
# Runtime: 84 ms, faster than 8.98% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.

そこまで速さは変わらないですね。

連結リストといえば、海外で有名なコーディング面接のバイブルともいうべきこの
世界で闘うプログラミング力を鍛える150問 _{トップIT企業のプログラマになるための本} (日本語) 単行本（ソフトカバー）
本にも連結リストは再起的な処理が多く苦手な人が多いと書いてありましたが、確かに普段の開発で連結リストを頻繁には使わないので解くのに時間がかかりました。

ちなみに上の本は古く、今は新しい版があるのでもし買うならこちらを
世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法
買うことをお勧めします。

良さげな書き方があれば追記します。