Sandbox::https://github.com/santom/leetcode/blob/master/algorithms/cpp/linkedListCycle/linkedListCycle.cpp

Repository navigation

32 lines (29 loc) · 1006 Bytes

// Source : https://oj.leetcode.com/problems/linked-list-cycle/

// Author : Hao Chen

// Date : 2014-07-03

/**********************************************************************************

* Given a linked list, determine if it has a cycle in it.

* Follow up:

* Can you solve it without using extra space?

**********************************************************************************/

* if there is a cycle in the list, then we can use two pointers travers the list.

* one pointer traverse one step each time, another one traverse two steps each time.

* so, those two pointers meet together, that means there must be a cycle inside the list.

bool hasCycle(ListNode *head) {

if (head==NULL || head->next==NULL) return false;

ListNode* fast=head;

ListNode* slow=head;

do{

slow = slow->next;

fast = fast->next->next;

}while(fast != NULL && fast->next != NULL && fast != slow);

return fast == slow? true : false;

}