備忘録 LeetCode-141.Linked List Cycle

警告
この記事を読む前に一度自身で解いてみてください．

はじめに

この記事はアルゴリズム振り返り用メモ，
言語化練習用に作成した記事です．

URL

Linked List Cycle

対象者

特になし

code

main.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //1つも要素がない場合
        if(head == NULL)return false;
        
        //fast = 2つ先
        //slow = 1つ先
        ListNode* fast = head;
        ListNode* slow = head;
        
        while(fast != NULL && fast->next != NULL){
            //要素更新
            fast = fast->next->next;
            slow = slow->next;    
            
            //一致チェック
            if(fast == slow)return true;
            
        }

        //不一致
        return false;
    }
};

結果

Runtime: 19 ms, faster than 38.14% of C++ online submissions for Linked List Cycle.
Memory Usage: 8.1 MB, less than 16.55% of C++ online submissions for Linked List Cycle.

詳細

赤:fastポインタ
青:slowポインタ

要素の数0~10,000

fastは2つ先の要素を
slowは1つ先の要素を
参照する

この2つの要素が一致した場合にtrueを不一致の場合にfalseを
返すアルゴリズムを書く

より詳細に

画像上のケースの場合

fastとslowは3から開始する．

ループ処理内では一致orfastがnullになるまで処理を続ける

fastがスタート位置から2つ進め0
slowもスタート位置から1つ進め2
一致していないのでもう一回ループ処理

fastを0から2つ進め2
slowを2から1つ進め0
一致していないのでもう一回ループ処理

fastを2から2つ進め-4
slowを0から1つ進め-4
一致したのでtrueを返して終了

参考

動画

おわりに

英語が苦手&LeetCodeに慣れていない事もあって想像以上に苦戦し約40分ぐらいかかりました．
今後の目標としてはこのレベルの問題を10分前後で解くことを目標にコツコツ解いていきます．