Created
May 17, 2021 03:26
-
-
Save adeydas/428e66ca58dbb4d537bce71f58a9c341 to your computer and use it in GitHub Desktop.
LinkedList cycle detection using Flyod algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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) { | |
// base case: if there are no nodes, there cannot be a cycle | |
if (head == null) { return false; } | |
// take 2 runners: the slow one starts at head and the fast one starts at one pointer beyond | |
ListNode slow = head; | |
ListNode fast = head.next; | |
// if slow and fast are equal, that means the fast pointer came across a cycle and caught up with the slow pointer | |
while (slow != fast) { | |
// if fast is null or fast.next is null, that means the fast ptr has reached the end of the list and hasn't hit any cycle | |
if (fast == null || fast.next == null) { | |
return false; | |
} | |
// slow ptr moves slowly by one increments | |
slow = slow.next; | |
// fast pointer moves fast by 2 increments | |
fast = fast.next.next; | |
} | |
return true; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment