Detect loop in Linked List

Multiple loop detection methods in a Linked List


Category: Data Structure And Algorithms Tags: C#

Detect Loop in Linked List - Code Files

Problem Statement

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

Linked List with loop
Fig 1: Linked List with loop

 

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

        hashSet.Add(temp);
        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);
    head.Next.Next.Next.Next = head.Next;

    Console.WriteLine($"{nameof(IsLoopDetected_UsingHash)}: {IsLoopDetected_UsingHash(head)}");
}

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; }
    // Additional flag
    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);
    head.Next.Next.Next.Next = head.Next;

    Console.WriteLine($"{nameof(IsLoopDetected_UsingCustomNodeStructure)}: {IsLoopDetected_UsingCustomNodeStructure(head)}");
}

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);
    head.Next.Next.Next.Next = head.Next;

    Console.WriteLine($"{nameof(IsLoopDetected_UsingFloydLoopDetection)}: {IsLoopDetected_UsingFloydLoopDetection(head)}");
}

Output

IsLoopDetected_UsingFloydLoopDetection: True

 


Like 0 People
Last modified on 3 July 2021
Nikhil Joshi

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

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x