141. Linked List Cycleの解答

解答１は思いついたが、2は思いつかなかった。よく思いつくなと思う  

 解答1：値を連想コンテナに保存して、比較する方法

1. リストの先頭の値がset内にあるか検索する
2. 見つからなかったら、リストの先頭の値をsetに保存する。
3. リストの次の値がset内にあるか検索する。これを値が見つかるまで繰り返す。

 /**
 * 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) {
        set<ListNode*> t;        
        while(head!=nullptr){
            if(t.find(head) == t.end()){
                t.insert(head);
            }else{
                return true;
            }
            head=head->next;
        }
        return false;
    }
};

解答2：1要素ずつ進むポインタと2要素ずつ進む2つのポインタを使い、この２つが重なるところがあるかを確認する方法

1.要素ポインタと2要素ポインタが同じ数値を確認する 2.違ったら、1要素ポインタは1要素進む、2要素ポインタは2進む。これを同じ値になるまで繰り返す。

 /**
 * 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) {
    if (head==nullptr){
      return false;
    }                   
 
     ListNode *slow = head, *fast = head;
        
     while (fast->next && fast->next->next) {
         slow = slow->next;
         fast = fast->next->next;
         if (slow == fast) {
             return true;
         }
    }
        
        return false;
    }
};