# Check if a LinkedList has a cycle

##### Problem Statement

Given a single linked list, verify if the list has a cycle.

A linked list has a cycle if a node's reference points back to an earlier node in the chain.

Example:

1 -> 2 -> 3 -> 4 -> 5

↑ _ _ _ _ ↓

###### Solution Explanation

Typically in a single linked list each node has a reference to a node forward in the chain, so every node can be visited only once in the chain, but if there's a cycle in the list, you will come across nodes more than once during the traversal.

Since we will be looking for a node which is visited twice, you can use a map to store all the visited nodes, and whenever there's a node which is already in the map, you can return true saying there's a cycle.

But this involves using additional space for the map or set. We can avoid this and detect if there exists a cycle simply by using an additional pointer which traverses the lists twice the speed as the regular list pointer.

Below is the java implementation of detecting cycle in linked lists,

```
public class LinkedListCycle {
public boolean doesCycleExist(ListNode head) {
if(head==null) return false;
ListNode walker = head, runner = head;
while(runner.next!= null && runner.next.next!=null){
walker = walker.next;
runner = runner.next.next;
if(walker==runner){
return true;
}
}
return false;
}
}
```

###### Time Complexity

The time complexity is O(n) since we do a single traversal across the list.

### Subscribe to Let's Talk Algorithms

Get the latest posts delivered right to your inbox