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;
 }
}

• JanDotNet: Do you use your own implementation of a linked list? As t3chb0t mentioned in a comment below, the .Net implementaion does not allow circular references.
• Eric Lippert: This is a standard interview problem, but I have never liked it, for several reasons. First, it relies upon an "aha" insight. Second, I have never once in real code accidentally circularized a linked list; it's an unlikely bug. Third, don't write bug detectors; write bug-free code to begin with. Fourth, this just tells you that a cycle exists, but what we would like to know is which is the node that needs to be detached! So, suppose you had to detect which node was the offending node; could you devise an algorithm to do that?

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; }
}

• t3chb0t: Would be so kind and explain to me how it works? I still don't get it after looking at it at ten times. To me a circular list is when LinkedList.First == LinkedList.Last but this is not possible since foo.AddLast(foo.First); throws an exception The LinkedList node already belongs to a LinkedList.. The circularity of a linked list here seems to be parapsychology ;-)
• JanDotNet: @t3chb0t: I suppose, that Scott uses the method IsCircular with his own linked list implementation that allows circular references (similar to the LinkedListNode class of my example).
• Marcel: @t3chb0t This works very well for me as is. However, it only works from bottom to top (from child to parent, so to speak). You will have to test for each child. This is very useful as a test when trying to add a new item to the set.
• Marcel: @t3chb0t This works very well for me as is, for a list that is possibly a tree (More than one node may link to a next item). However, it only works from bottom to top (from child to parent, so to speak). You will have to test for each child. This is very useful as a test when trying to add a new item to the 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;
}

• t3chb0t: You seem to know what it is about ;-] do you mind explaining what kind of a linked-list it is? Do you think it's OP's own implementation too?
• 200_success: @t3chb0t I've assumed that it's some custom Node class with a Next member.