Linked List with Reverse Traversal and Floyd Detection Algorithm

 

🔁 Linked List in C#: Loop Detection using Floyd’s Algorithm + Reverse Traversal

Linked Lists are one of the most important data structures in programming and are frequently asked in interviews. In this article, we’ll cover a practical and important concept — detecting a loop in a linked list using Floyd’s Cycle Detection Algorithm, along with reverse traversal using recursion.

---

📌 What is a Linked List?

A Linked List is a linear data structure where each element (node) contains:

• Data

• A reference (pointer) to the next node

Unlike arrays, elements are not stored in contiguous memory.

---

⚠️ What is a Loop in a Linked List?

A loop occurs when a node points back to a previous node instead of pointing to null.

Example:

10 → 20 → 30 → 40
                    ↑      ↓
                    ← ← ← ← ←

This creates an infinite cycle, which can break normal traversal logic.

---

🚀 Why Do We Need Loop Detection?

• Prevent infinite loops during traversal

• Avoid application crashes

• Important for debugging memory issues

• Common interview problem

---

🧠 Floyd Cycle Detection Algorithm (Tortoise & Hare)

This is the most efficient way to detect a loop.

🔍 Concept:

• Use two pointers:

  • Slow pointer → moves 1 step

  • Fast pointer → moves 2 steps

✔️ Logic:

• If there is a loop → they will meet

• If no loop → fast pointer reaches null

⏱️ Complexity:

• Time: O(n)

• Space: O(1)

---

🔁 Reverse Traversal using Recursion

Instead of reversing the list, we can print it in reverse order using recursion:

• Go till the last node

• Print while returning back

⚠️ Important: This should only be done if no loop exists, otherwise it will cause infinite recursion.

---

💻 Complete Implementation in C#

using System;

public class Node
{
    public int Data;
    public Node Next;

    public Node(int num)
    {
        Data = num;
        Next = null;
    }
}

public class LinkedList
{
    public Node head;

    // Add node at end
    public void AddNode(int num)
    {
        Node newNode = new Node(num);

        if(head == null)
        {
            head = newNode;
            return;
        }

        Node current = head;
        while(current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }

    // Create loop (last node points to node with value 30)
    public void CreateLoop()
    {
        if(head == null)
            return;

        Node loopNode = null;
        Node temp = head;

        while(temp.Next != null)
        {
            if(temp.Data == 30)
            {
                loopNode = temp;
            }
            temp = temp.Next;
        }

        if(loopNode != null)
        {
            temp.Next = loopNode;
        }
    }

    // Detect loop using Floyd Algorithm
    public bool DetectLoopByFloydAlgorithm()
    {
        Node slow = head;
        Node fast = head;

        while(fast != null && fast.Next != null)
        {
            slow = slow.Next;
            fast = fast.Next.Next;

            if(slow == fast)
                return true;
        }

        return false;
    }

    // Reverse traversal using recursion
    public void ReverseTraversal(Node node)
    {
        if(node == null)
            return;

        ReverseTraversal(node.Next);
        Console.WriteLine(node.Data);
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        LinkedList list = new LinkedList();

        list.AddNode(10);
        list.AddNode(20);
        list.AddNode(30);
        list.AddNode(40);

        list.CreateLoop();

        bool hasLoop = list.DetectLoopByFloydAlgorithm();

        Console.WriteLine(hasLoop ? "Loop detected" : "No Loop detected");

        // Only perform reverse traversal if no loop exists
        if(!hasLoop)
        {
            list.ReverseTraversal(list.head);
        }
    }
}

---

✅ Key Takeaways

• Floyd Algorithm is the most efficient way to detect loops

• Uses two pointers (slow & fast)

• No extra memory required

• Always check for loop before traversal

• Reverse traversal using recursion is clean but must be used carefully

---