Check a Linked List for Loops or Cycles With O(1) Space Complexity

Check if a given linked list has cycles. Try to achieve O(n) runtime with a space complexity of O(1). If there is a cycle, return true otherwise return false. Consider empty lists as non cyclic.

Examples:
1->2->3->4->1 ==> true
1->2->3->4 ==> false

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

The key here is to use two temporary pointers, one of them traverses the list one node at a time and the other one traverses the list two nodes at a time. If the pointers collide, there is a loop.

Final hint! You should be able to code the problem on viewing this.

Try the Floyd Cycle Finding Algorithm, also known as the 'Tortoise & Hare Algorithm'. In this approach, you maintain two pointers - 'slow' & 'fast' where slow moves one node at a time and fast moves two nodes at a time. If there is a cycle, these two pointers will inevitably meet! Seriously, they will.

public Boolean isCyclic(ListNode head) {
    



}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Check a Linked List for Loops or Cycles With O(1) Space Complexity

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :