How to determine if a linked list has a cycle using only two memory locations

by

I would suggest using Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm. It has O(n) complexity and I think it fits your requirements.

Example code:

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

More info on Wikipedia: Floyd’s cycle-finding algorithm.

More Related Contents:

  1. How does finding a cycle start node in a cycle linked list work?
  2. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  3. Looping in a spiral
  4. Merge Sort a Linked List
  5. What’s the fastest algorithm for sorting a linked list?
  6. Best algorithm to test if a linked list has a cycle
  7. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  8. How to apply binary search O(log n) on a sorted linked list?
  9. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  10. How to determine if a point is in a 2D triangle? [closed]
  11. How does the Google “Did you mean?” Algorithm work? [closed]
  12. How to detect a loop in a linked list?
  13. How to find all combinations of coins when given some dollar value [closed]
  14. Data structures for loaded dice?
  15. Writing your own square root function
  16. How do you like your primary keys? [closed]
  17. Generating permutations lazily
  18. How to read values from numbers written as words?
  19. Sorting in place
  20. Programming Riddle: How might you translate an Excel column name to a number?
  21. fitting n variable height images into 3 (similar length) column layout
  22. Given a number, produce another random number that is the same every time and distinct from all other results
  23. Painter puzzle – algorithmic estimation from first principles
  24. Polynomial time and exponential time
  25. How to count integers between large A and B with a certain property?
  26. Why is depth-first search claimed to be space efficient?
  27. How can I convert between a double-double and a decimal string?
  28. Which is faster, Hash lookup or Binary search?
  29. Finding groups of similar strings in a large set of strings
  30. Tournament bracket placement algorithm

Leave a Comment