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