# Multiple loop detection methods in a Linked List

 Category: Data Structure And Algorithms Tags:

## Problem Statement

Find a loop in given linked list. Suppose a linked list given as below.

A method should be written to return True if linked list has any loop.

### Method 1: Using HashSet - Complexity: O(n)

We can store visited nodes in HashSet while traversing the list. If an item is revisited then list has loop, if null is detected then list does not have any loop. Look at the code below.

```public class Node
{
public int Value { get; set; }
public Node Next { get; set; }

public Node(int value)
{
Value = value;
}
}```
```static bool IsLoopDetected_UsingHash(Node head)
{
HashSet<Node> hashSet = new HashSet<Node>();
var temp = head;

while (temp != null)
{
if (hashSet.Contains(temp))
{
return true;
}

temp = temp.Next;
}

return false;
}```

Running above code.

```static void Main(string[] args)
{
/*
* head -> 1 -> 2 -> 3 -> 4
*              ↑_________|
*              loop
*/
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Next = new Node(3);
head.Next.Next.Next = new Node(4);

}```

Output

IsLoopDetected_UsingHash: True

### Method 2: Modify Node structure - Complexity: O(n)

We can add a new boolean property in Node to track visited nodes. If a visited node appears again while traversing then we have loop in the linked list.

```public class CustomNode
{
public int Value { get; set; }
public CustomNode Next { get; set; }
public bool IsVisited { get; set; } = false;

public CustomNode(int value)
{
Value = value;
}
}```
```static bool IsLoopDetected_UsingCustomNodeStructure(CustomNode head)
{
var temp = head;

while (temp != null)
{
if (temp.IsVisited)
{
return true;
}

temp.IsVisited = true;
temp = temp.Next;
}

return false;
}```

Running above code.

```static void Main(string[] args)
{
CustomNode head = new CustomNode(1);
head.Next = new CustomNode(2);
head.Next.Next = new CustomNode(3);
head.Next.Next.Next = new CustomNode(4);

}```

Output

IsLoopDetected_UsingCustomNodeStructure: True

### Method 3: Using Floyd Loop Detection Algorithm - Complexity: O(n)

We can have two pointers, one pointer can be fast pointer which jumps two nodes at a time and another one can be the normal one which jumps only one node at a time. When we traverse a list which has loop, then both pointers must meet at some node.

```static bool IsLoopDetected_UsingFloydLoopDetection(Node head)
{
var normalPointer = head;
var fastPointer = head?.Next;

while (fastPointer != null)
{
if (normalPointer == fastPointer)
{
return true;
}

normalPointer = normalPointer?.Next;
fastPointer = fastPointer?.Next?.Next;
}

return false;
}```

Running above code.

```static void Main(string[] args)
{
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Next = new Node(3);
head.Next.Next.Next = new Node(4);

}```

Output

IsLoopDetected_UsingFloydLoopDetection: True

 Like 0 People
 Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 146 Questions: 16 Given Best Solutions: 16 *