Linked List Cycle
Problem Statement
Published in
1 min readOct 22, 2015
Given a linked list, determine if it has a cycle in it. Follow up:
Can you solve it without using extra space?
Approach
Using Floyd Cycle Detection Algorithm, we can find the loop in a linked list. Lets start with 2 pointers
- Slow pointer that moves 1 node at a time
- Fast pointer that moves 2 nodes at a time.
Keep moving these pointers until either :
- Fast pointer becomes null which means that there is no cycle in the linked list.
- OR
- Fast pointer and Slow pointer meet which means that there is a cycle.
Note: If there exists a cycle then Slow pointer and Fast pointer will definitely meet. At this point the slow pointer will be inside the loop.
The run time complexity of this Solution is O(n)
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
ListNode turtle = head;
ListNode rabbit = head;
while(rabbit != null && rabbit.next != null){
turtle = turtle.next;
rabbit = rabbit.next.next;
if(turtle == rabbit){
return true;
}
}
return false;
}
}