LeetCode: 141. Linked List Cycle

問題の要約

連結リストにサイクルがあるか判断する問題
※サイクル:連結リストのループがあり、次のリストへ辿っていくと一度通ったリストへ戻る

問題

問題へのリンク

回答１　ブルートフォース的な末尾確認

リストの次要素へ１万回遷移して末尾確認。1万回遷移後に末尾がなければ、サイクルはあるとみなすやり方で回答

bool hasCycle(ListNode *head) {
    for(int i=0;i<10000;i++){
        if(head == NULL){
            return false;
        } 
        head = head->next;
    }
    return true;
}

Runtime: 12 ms
Memory usage: 9.7 MB
提出でAcceptされたが、力任せの実装であり、サイクルがあるかどうかは具体的に判断してないので達成感なし

回答２　リストの書き換え

次に、通過した連結リストの中身は書き換えるやり方で回答。次リストへの遷移で書き換えた内容に当たったら、サイクルはあるとみなす。

class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        if(head==NULL || 
           head->val==NULL) {
            return false;
        }
        while (head->next!=NULL) {
            if(head->val==NULL) {
                return true;
            }
            head->val=NULL;
            head = head->next;
        }
        return false;
    }
}

Runtime: 12 ms
Memory Usage: 9.7 MB

提出でAcceptされた。Runtime時間は意外にも回答１と変わらなかったです。