Detecting cycle in LinkedList

Question

Is this a fair/clean way to detect a cycle in a LinkedList? Should work for both single and double LinkedLists'.

public bool IsCircular()
{
    if (Head != null && Head.Next != null)
    {
        var slow = Head;
        var fast = Head.Next;
        while (slow.Next != null && fast.Next != null && fast.Next.Next != null)
        {
            if (slow == fast)
            {
                return true;
            }
            slow = slow.Next;
            fast = fast.Next.Next;
        }
        return false;
    }
    else
    {
        return Head != null ? (Head == Head.Next) : false;
    }
}

Answer 1

It detects a cycle very nicely. However, I've got a few remarks:

Personally I would rename your heads to slowHead and fastHead. The expression slowHead == fastHead makes more sense then.

Your else block will always return false though. So you can get rid of that and replace it with return false. If you do that, the return false after the while loop can be removed as well.

Answer 2

The method seems to work fine, but I had to read it twice before I understand how it works. Another approch is to traverse the linked list and store the visited items to check if it was visited twice:

public bool IsCircular(LinkedListNode head)
{
    var current = head;
    var visited = new HashSet<LinkedListNode>();
    while(current != null)
    {
        if (!visited.Add(current))
            return true;
        current = current.Next;
    }
    return false;
}

public class LinkedListNode
{
    public LinkedListNode Next { get; set; }
    public object Value { get; set; }
}

Answer 3

@venerik had already covered the majority of the code, however I think it's worth mentioning that checking:

slow.Next != null

In your while loop is redundant. The slow pointer is always going to be behind the fast pointer, which has already performed the null checks.

Answer 4

The special cases are excessively complicated:

if (Head != null && Head.Next != null)
{
    // ...
}
else
{
    return Head != null ? (Head == Head.Next) : false;
}

The else clause is reached only if either Head or Head.Next is null, in which case it returns either false or (Head == Head.Next), respectively. But since Head is non-null and Head.Next is null, (Head == Head.Next) will always be false. So, the function should be simplified to:

public bool IsCircular()
{
    if (Head == null || Head.Next == null) return false;
    var slow = Head;
    var fast = Head.Next;
    while (slow.Next != null && fast.Next != null && fast.Next.Next != null)
    {
        // ...
    }
    return false;
}

But || Head.Next == null can also be dropped, since it is handled by the slow.Next != null check in the while loop.

public bool IsCircular()
{
    if (Head == null) return false;
    var slow = Head;
    var fast = Head.Next;
    while (fast != null && fast.Next != null)
    {
        if (slow == fast) return true;
        slow = slow.Next;
        fast = fast.Next.Next;
    }
    return false;
}