Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Created October 17, 2016 02:09
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/f17595567a34e2910837e322e68d280e to your computer and use it in GitHub Desktop.
Save kartikkukreja/f17595567a34e2910837e322e68d280e to your computer and use it in GitHub Desktop.
Detecting cycle in a linked list
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;
int length = 1;
for (fast = fast->next; fast != slow; fast = fast->next, length++);
for (fast = A; length > 0; fast = fast->next, length--);
for (slow = 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