Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Created October 17, 2016 01:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kartikkukreja/ae74298ade0e585511ded43c0519471a to your computer and use it in GitHub Desktop.
Save kartikkukreja/ae74298ade0e585511ded43c0519471a to your computer and use it in GitHub Desktop.
Detecting a cycle in a linked list with Floyd's cycle-finding algorithm
ListNode* detectCycle(ListNode* A) {
if (A == NULL || A->next == NULL || A->next->next == NULL) return NULL;
ListNode *slow = A, *fast = A;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
break;
}
if (slow != fast) return NULL;
for (fast = A; slow != fast; slow = slow->next, fast = fast->next);
return slow;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment