142.Linked list cycle 2の解答

Linked list cycle 2https://leetcode.com/problems/linked-list-cycle-ii/ 2はループの有無ではなくループの始まる数字を答える問題。

setを使用した解答 setを使う場合は、配列の数字を頭から比較するだけなので1と同じ考え方でよかった。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr){
            return nullptr;
        }

        set<ListNode*> temp;
        
        while(head!=nullptr){
            if(temp.find(head)==temp.end()){
                temp.insert(head);                  
            }else{
              return head;
            }            
            head = head->next;
        }
        return nullptr;
    }
};

ポインタを使用した解答 ポインタのほうは少し異なり、2つのポインタを使うのは同じだが、2つのポインタが重なった位置がループの開始位置とは限らないので、開始位置を探す必要がある。回答を見たが下記部分の意味が分からなかったので、説明を探した。

 slow=head;
    while(slow!=fast){
         fast=fast->next;
         slow=slow->next;
    }

下記のblogがとてもわかりやすかった。 mhiro216.hatenablog.com

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr) return nullptr;
        ListNode *slow=head, *fast=head;
        while(fast !=nullptr && fast->next != nullptr){
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){
                while(slow!=head)
                {
                    slow=slow->next;
                    head=head->next;
                }                
                return slow;
            }
        }
        return nullptr;
    }
};