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; } };