Skip to main content

Detect and remove loop of linked list in c#

Csharp program for Detect and remove loop of linked list. Here problem description and other solutions.

// Include namespace system
using System;
// Csharp program for
// Detect and remove loop in a linked list

// Linked list node
public class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public SingleLL()
	{
		// Set head 
		this.head = null;
	}
	// Add new node at the end of linked list
	public void insert(int value)
	{
		// Create a node
		var node = new LinkNode(value);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			var temp = this.head;
			// Find last node
			while (temp.next != null)
			{
				// Visit to next node
				temp = temp.next;
			}
			// Add node at last position
			temp.next = node;
		}
	}
	// Display all Linked List elements
	public void display()
	{
		if (this.head != null)
		{
			var temp = this.head;
			while (temp != null)
			{
				// Display node value
				Console.Write("  " + temp.data.ToString());
				// Visit to next node
				temp = temp.next;
			}
		}
		else
		{
			Console.WriteLine("Empty Linked list");
		}
	}
	// Delete loop
	public LinkNode deleteLoop(LinkNode temp)
	{
		// Base condition
		if (temp == null || temp.next == null)
		{
			return null;
		}
		var hold = temp.next;
		// Important to break recursion
		temp.next = null;
		temp.next = this.deleteLoop(hold);
		return temp;
	}
	// Detecting loop of linked list
	public void detectLoop()
	{
		if (this.head == null)
		{
			Console.WriteLine("Empty Linked List ");
			return;
		}
		var first = this.head;
		var second = this.head;
		while (second != null && 
               second.next != null && 
               second.next.next != null)
		{
			// Visit to next node
			first = first.next;
			// Visit to second next node
			second = second.next.next;
			if (first == second)
			{
				// loop is found
				Console.WriteLine("Loop Found");
				// Then delete loop
				this.deleteLoop(this.head);
				return;
			}
		}
		// When no loop
		Console.WriteLine("Loop not exist");
	}
	public static void Main(String[] args)
	{
		var sll = new SingleLL();
		// Linked list
		// 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
		sll.insert(1);
		sll.insert(2);
		sll.insert(3);
		sll.insert(4);
		sll.insert(5);
		sll.insert(6);
		sll.insert(7);
		// Case A
		// When no loop
		sll.detectLoop();
		// Create loop for testing
		sll.head.next.next.next.next.next.next.next = sll.head.next;
		// Case B
		// When loop
		sll.detectLoop();
		Console.WriteLine("Linked List");
		// After remove loop, linked list is
		sll.display();
	}
}

Output

Loop not exist
Loop Found
Linked List
  1  2  3  4  5  6  7




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment