# Challenge

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

• Can you solve it using $$\O(1)\$$ (i.e. constant) memory?
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

{
public class ListNode
{
public int val;
public ListNode next;

public ListNode(int x)
{
val = x;
}
}

[TestClass]
public class HasCycleTest
{
[TestMethod]
public void HasCycle()
{
}

[TestMethod] public void NoCycle()
{
}

[TestMethod]
public void OneItem()
{
}
}

public class HasCycleClass
{
{
{
return false;
}
while(fast!= null)
{
if (fast == slow)
{
return true;
}
else
{
slow = slow.next;
if (fast.next == null)
{
return false;
}
fast = fast.next.next;
}
}

return false;
}
}
}

• @dfhwze thanks I added the class – Gilad Aug 12 at 19:43

### Performance

You have implemented Floyd’s Cycle-Finding Algorithm which adheres to $$\0(1)\$$ storage space. An alternative exists Brent’s Cycle Detection Algorithm which uses the same storage space. Check out this review on Computer Science SE for a comparison. It appears in general, Brent's algorithm is faster.

According to Brent's paper, the complexity of Floyd's algorithm is between 3max(m,n) and 3(m+n), and that of Brent's is at most 2max(m,n)+n, which is always better than 3max(m,n).

courtesy of Yuval Filmus' answer at CS

### Style Guidelines

• use var to declare a variable, specially when the type can be inferred from code
• use a separate line for declaring attributes on top of members
• use a white space after a method name and the opening parenthesis
• use a white space after the while statement
• use white space around operators (!=)
• remove redundant nested else branches if the if branch always performs a return
• cool! I didn't know that one – Gilad Aug 12 at 20:18

For ListNode class, I would expect val and next to be named Value and Next. I would also rather see them be properties instead of fields. And for some reason, I am expecting to see a Previous property as well.
If the exercise was to create your own linked list, then I would want to see 2 different classes. One would be the ListNode for individual nodes. The other would be a LinkedList, which is a collection of ListNode. Then the method in the HasCycleClass could be moved as a member to LinkedList. As you have it, it feels awkward to have the HasCycleClass where it is.
If the exercise was simply to create an efficient HasCycle method, I would prefer to see you use .NET's LinkedList and LinkedListNode classes.