# 141 - Linked List Cycle

## 解法一 - Fast & Slow pointer

``````/**
* 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) {
ListNode* slow = head;
ListNode* fast = head;

while(fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;

if(slow == fast) {
return true;
}
}

return false;
}
};
``````

## 解法二 - Hash 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) {
unordered_set<ListNode*> nodeSeen;

while(head != nullptr) {
if(nodeSeen.find(head) != nodeSeen.end()) {
return true;
}
else {
}

}

return false;
}
};
``````

## 延伸題 - linked list cycle length

``````using namespace std;

#include <iostream>

class ListNode {
public:
int value = 0;
ListNode *next;

ListNode(int value) {
this->value = value;
next = nullptr;
}
};

public:
static int findCycleLength(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast)  // found the cycle
{
return calculateLength(slow);
}
}
return 0;
}

private:
static int calculateLength(ListNode *slow) {
ListNode *current = slow;
int cycleLength = 0;
do {
current = current->next;
cycleLength++;
} while (current != slow);
return cycleLength;
}
};

int main(int argc, char *argv[]) {
ListNode *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = new ListNode(6);