Blind 75 - Linked List Cycle
Have a fast pointer and a slow pointer. fast increases by 2. slow increases by 1. if both become the same then the cycle exists. if fast one reaches end then no cycle exists.
[Video]
Check if the given LinkedList is cyclic.
Approaches
O(n) time complexity; O(1) space complexity
Have a fast pointer and a slow pointer. fast increases by 2. slow increases by 1. if both become the same, then the cycle exists. if fast one reaches the end then no cycle exists.
Lines of code: 16
public boolean hasCycle(ListNode head) {
if(head == null) { return false;}
ListNode slow = head;
ListNode fast = head;
while(fast !=null){
slow = slow.next;
fast = fast.next;
if(fast==null){ break;}
else {fast=fast.next;}
if(slow == fast){ return true; }
}
return false;
}
Line 1: head null check is unnecessary; Line 18: can be removed by adding the fast.next, check in while loop itself.
Optimized solution below
Optimized solution
Source: Java: Fast-Slow Pointer Method - LeetCode Discuss
Lines of code 8:
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast !=null && fast.next !=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){ return true; }
}
return false;
}
Without 2 pointers solution
Source: Java O(1) Memory solution - LeetCode Discuss
Modify the value in the list to something that can’t occur. Check if the current value is that value.
public boolean hasCycle(ListNode head) {
while (head != null) {
if (head.val == 1_000_000) return true;
head.val = 1_000_000;
head = head.next;
}
return false;
}