** Ashish Srivastava** | @ashishsrtechie | 23 Jan, 2016

John, an interviewee had been working hard for his big day with Yahoo. An interviewer calls him and after a brief introduction, asks him another classic; can you detect a loop in a singly linked list ?

How should have John handled this ?

This classic is also know as cycle detection problem. To learn more about it, refer this wiki link.

Let us discuss the possible solutions.

**Approach 1**

**Hint: Keep track of all the nodes visited**

**Implementation:**

**Approach 2**

**Hint: Two nested traversals to check for nodes already visited**

**Implementation:**

**Approach 3**

**Hint: Detect cycles in two passes**

**Implementation:**

**To solve such questions and prepare for coding interviews - log on to firecode.io**

Think you have more efficient or better solution? share it in the comments!

How should have John handled this ?

This classic is also know as cycle detection problem. To learn more about it, refer this wiki link.

Let us discuss the possible solutions.

Store all the nodes visited in a hashset or any other preferred data structure and check each node’s existence within this hashset, if found, we have a cycle in the list.

// Data structure to store nodes HashSet nodeSet = new HashSet(); Node temp = head; While(temp.next != null) { if(nodeSet.contains(temp)) { return true; } else { nodeSet.add(temp); } temp = temp.next;

We need to traverse through the node only once, hence time complexity is O(n); however, we do need extra space O(n) to solve through this approach.

Let us see if we can avoid the space complexity.// Nested traversals while(temp.next != null) { Node temp2 = head; while(temp2.next != temp) { if(temp2 == temp) { return true; } temp2 = temp2.next; } temp = temp.next; }

This pseudocode is inefficient because even though it has the space complexity O(1), it has a worst case time complexity of O(n^{2}).

Use two iterators to traverse through the list, one iterating one node at a time and the other iterating 2 nodes at a time. If they both match then, the list is cyclic.

ListNode slow = head, fast = head; while(slow != null && fast !=null) { // Slow move 1 node slow = slow.next; // Fast moves 2 nodes if(fast.next != null) { fast = fast.next.next; } else { break; } //if slow and fast meet, then there is a loop if(slow == fast) { return true; } } return false;

This solution has the time complexity of O(n) and space complexity of O(1). This algorithm is also known as "Floyd’s Cycle-Finding Algorithm".

Though computing is not as expensive as it used to be before, a good programmer must always strive for an efficient answer.