Finding a Cycle in A Linked List 🐢 🐇 - Leetcode Solution in Java

In this article, you will learn how to find a linked list. I have found this same coding problem on Leetcode and HackerRank. You can use either to follow along because it's the same algorithm, though the names for the types on Leetcode and Hackerrank differ. I will be referencing Leetcode's problem for this article.

Cycle Detection and Understanding Cycles in a Linked List

Cycle detection is used to find cycles in a sequence. So, a linked list has a cycle when implementing and traversing through a linked list with two pointers.

Floyd's Cycle

Floyd's Cycle algorithm, also known as the tortoise and hare algorithm, is one algorithm that is used to detect whether a linked list or array has a cycle in it. The reason it has this latter name is that you will be using two pointers: one slow and one fast. If a cycle does exist, the fast one(hare) will eventually meet up with the slow one(tortoise). So while the tortoise is trying to get to the end of the linked list, the hare keeps traveling through the linked list over and over until one of the two conditions is met: the hare and tortoise have met up at the same point, or the tortoise has reached the end of the linked list. If the hare has met up with that tortoise, then a cycle exists, but if not, no cycle exists in the linked list. Now that the algorithm has been explained, let's solve this problem.

Approach and Solution

As I stated at the beginning, I will be using Leetcode, but you can use Hackerrank. The only difference is that Leetcode's implementation of the Linked List is named differently compared to Hackerrank.

Cycle Detection - Hackerrank

141. Linked List Cycle - Leetcode

So, looking back at what we now know about Floyd's algorithm and the tortoise and hare comparison, what do you think is the first thing you should do?

You would first implement two List Nodes called slow and fast(or you could call them tortoise and hare if you want to be cute about it 💜).

ListNode fast = head; //value of head;
ListNode slow = head; //value of head;

Now that you have your two List Nodes, you would use a while loop to traverse through the linked list. Remember how the earlier example of the hare keeps cycling through the linked list until it catches up with the tortoise? The condition for the while loop would be that while the slow node is not null, the fast node is not and the node after the fast node is not null then, keep these two nodes traversing.

 // while(slow is not null, fast is not null, and next node after fast is not null)THEN:
while(slow != null && fast != null && fast.next != null) {
...
}

Finally, we get to the most important part which is the traversing of both the list nodes. Our slow pointer is going to traverse through the linked list till it reaches the tail one list node at a time while the fast pointer is going to traverse twice as fast and if slow is equal to fast, then the cycle exists.

while(slow != null && fast != null && fast.next != null) {
    //slow equals slow's next node;
    slow = slow.next;

    //fast equals fast's 2nd next node;
    fast = fast.next.next;

    //if(slow is equal to fast)THEN true;
    if(slow == fast) return true;
}

The Full Code Solution

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//Time Complexity: O(n)
//Space Complexity: O(1)
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head; // 🐇
        ListNode slow = head; // 🐢

        while(slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast) return true;
        }

        return false;
    }
}

Congratulations on successfully grasping another challenging problem in Data Structures and Algorithms!