LeetCode 1000000本ノック【141. Linked List Cycle】

目次

No.	項目
1	概要
2	問題
3	解法
4	エラー対応

概要

●発端
　・競プロ初心者、コーディング面接でズタボロにされ、
　・最低限のアルゴリズム学習とコーディング力強化を習慣化するため記事化
●環境
　・LeetCodeブラウザ上で実装（vscodeに拡張機能にするかもシレナイ）
　・言語はpython3
●その他ルール
　・google検索は自由に（直接的なLeetCodeの問題解説ページはNG）
　　（60分実装して実装出来なければ解説ページ参照）
　・コーディング面接対策のために解きたいLeetCode 60問から問題選出
　・「1000000」は任意の2進数とする

問題

• 141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

⇨「引数に渡された連結リストがサイクルを持っていれば（循環していれば）Trueを、そうでなければFalseを返せ」と書いています。知らんけど。

Input: head = [3,2,0,-4], pos = 1 Output: true

解法

実施時間：30分

「LinkedList」で検索した下記ページを参考~~（というかほぼ答え）~~
LinkedListが輪になっているかを判定する Hacker Rank

考え方としては、連結リストに２つのポインターを置いて別々の間隔で進め、
もし途中で一致したなら循環しているというもの。知らんけど。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        slow = head
        fast = head.next
        while fast is not None and fast.next is not None and slow.next is not None:
            if fast == slow:
                return True
            slow = slow.next
            fast = fast.next.next
        return False

渡された連結リストが上記例題だとすると
fastポインター（1つ飛ばしで進む） 2 → -4　→ 2 → -4
slowポインター（順番に進む）　　 3 →　2　→ 0 → -4

※pos = 1なのでlist[1]の2に循環
※pos = ここで一致するためTrue

エラー対応

●while文の条件不足でRuntime Error
　・要素数1の想定漏れ。fastポインターがnextから始まってるからそりゃあね...

Input: head = [1], pos = -1

Bad

while fast.next is not None and slow.next is not None:

good

while fast is not None and fast.next is not None and slow.next is not None:

●if文の条件記載ミスでWrong Answer
　・リスト内の値は重複しないという思い込み実装...
Input: head = [1,1,1], pos = -1

Bad

if fast.val == slow.val:

good

if fast == slow: