How to detect a loop in a linked list

Given a linked list, check if it has a circle in it or not

 

Example 1

Input: Node1 -> Node2 -> Node3

Output: false

Example 2

Input: Node1 -> Node2 -> Node3 -> Node4 -> Node2

Output: true

 

/* Definition for ListNode
public class ListNode
{
    public int Value;
    public ListNode Next;

    public ListNode(int x)
    {
        Value = x;
    }
}
*/
public class Solution
{
    public bool HasCycle(ListNode head)
    {
    }
}

A linked list has a cycle if a node in the list can be reached again by continuously following the next pointer. Let's see an example.

The linked list has a loop, node 4 connects to node 2

HashSet approach

The idea is to traverse thru the linked list and check if a node has already been visited. If a node has already been seen, it means we found a loop. To implement this approach, we will use the HashMap. The algorithm is easy to implement, it has only one downside, it uses O(n) space to store nodes.

Code

    public bool HasCycle(ListNode head)
    {
        HashSet<ListNode> cache = new HashSet<ListNode>();
        while (head != null)
        {
            if (cache.Contains(head))
            {
                return true;
            }
            cache.Add(head);
            head = head.Next;
        }
        return false;
    }

Time complexity: O(n)

Space complexity: O(n)

Floyd's tortoise and hare

This approach uses two pointers: a slow pointer (tortoise) and a fast pointer (hare) to determine if a linked list has a loop. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If a loop exists in the linked list, the fast and slow pointers meet at some point. This approach is called - Floyd's cycle-finding algorithm. This algorithm is better than HashSet approach. Both algorithms have the same time complexity, O(n) , but Floyd's cycle-finding algorithm uses O(1) space compared to the HashSet approach, which uses O(n) space.

Code

    public bool HasCycle(ListNode head)
    {
        if (head == null || head.Next == null)
        {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

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

            if (slow == fast)
            {
                return true;
            }
        }

        return false;
    }

Time complexity: O(n)

Space complexity: O(1)