Best algorithm to test if a linked list has a cycle

by

Have two pointers iterating through the list; make one iterate through at twice the speed of the other, and compare their positions at each step. Off the top of my head, something like:

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n), which is as good as you can get.

More Related Contents:

  1. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  2. How to apply binary search O(log n) on a sorted linked list?
  3. How to create the most compact mapping n → isprime(n) up to a limit N?
  4. Reverse the ordering of words in a string
  5. How to create the most compact mapping n → isprime(n) up to a limit N?
  6. How to reverse a singly linked list using only two pointers?
  7. Hash table runtime complexity (insert, search and delete)
  8. How does finding a cycle start node in a cycle linked list work?
  9. What’s the fastest algorithm for sorting a linked list?
  10. How do you validate a binary search tree?
  11. design a stack such that getMinimum( ) should be O(1)
  12. How to delete in a heap data structure?
  13. What is the difference between tree depth and height?
  14. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  15. insert, delete, max in O(1)
  16. O(klogk) time algorithm to find kth smallest element from a binary heap
  17. In Order Successor in Binary Search Tree
  18. Skip List vs. Binary Search Tree
  19. Algorithm for autocomplete?
  20. What is the advantage to using Bloom filters?
  21. Why does Dijkstra’s algorithm use decrease-key?
  22. Merging two sorted linked lists
  23. How can I return an array of struct in solidity?
  24. Search a sorted 2D matrix [duplicate]
  25. The intersection of all combinations of n sets
  26. Why are hash table expansions usually done by doubling the size?
  27. Algorithm for merging two max heaps?
  28. What are probabilistic data structures?
  29. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  30. Why is vector array doubled?

Leave a Comment