Detect a loop in a Linked List
  • node
  • stackqueuelinkedlist
  • linkedlist
  • loop
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2551)

Write a function to detect a loop in a Linked List.


Posted Answers

We can detect whether there is any loop in the Linked List by


  • Create two references - \( slow \) and \( fast \).
  • Start from the beginning of the list. \( slow \) hops one node while \( fast \) hops two.
  • If they meet, loop is found.

public boolean  hasLoop(Node first){

/* Linked List doesn't exist - so no loop */
if(first == null)
return false;

/* Create two reference */
Node slow, fast;

/* Both start from the beginning of the Linked List */
slow = fast = first;
while(true){
/* One hop */
slow = slow.next;
if(fast.next! = null)
/* Two hops */
fast = fast.next.next;
else
return false;

/* If slow or fast either hits null - no loop */
if(slow == null || fast == null)
return false;

/* if slow and fast meet - Bingo! loop found */
if(slow == fast)
return true;
}
}

You need to Sign In to post your solution.