In this article, we will look at an interesting problem related to Linked List . ‘Given a Single Linked List, Remove Loop if there exists any’. We will look at different ways to solve this problem and analyze the complexities of our approach.
Now, To Remove a Loop in a Linked List, we need to first Detect a Loop in the linked list. If a Loop exists we remove it with our logic and print the elements of the list. So having a Loop in a Linked List means there is no such node having a NULL pointer or reference. In simpler terms, the Linked list has no end. Let us understand this with an example.
Here, we have a Linked List with 5 nodes, Node 12 is the Head node. We can see a Loop exists in the list connecting nodes 25 and 99. So we need to Remove this Loop such that the last node (25) points to NULL. After removal the List should look like this:
We can see the last node now points to NULL and the loop no longer exists. Now, let us look at different approaches to solve the problem.
Note: If the Loop starts from any other node except the last node we need to change its reference to NULL to remove the loop.
Approach 1 (Using Hashing Concept)
- In this approach we will hash or store the references of each node of the Linked List in a Unordered Set or Hash-Set in Java, which contains Unique elements.
- So, we will traverse the list node by node add it to our Set, if not present. We will have a Pointer/Variable prev which will hold the previous node reference and every time we add the node to the Set, we update the prev to Current Node’s reference or address.
- When we encounter a node pointing to a node already present in the Set, we know that we encountered a loop so the set will already have the node when we try to add it.
- Hence in that case we do not add the node again, we make the last node or prev point to NULL. Thereby, removing the loop in the linked list.
Let us look at the implementation of above in java:
import java.util.*;
class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
public class LinkedList
{
static Node head; // head node
// print the linked list elements
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
// Returns true if the loop is removed from the linked list else returns false.
static boolean detectandRemoveLoop(Node head)
{
Set<Node> hs = new HashSet<Node>();
Node prev = null;
Node curr = head;
while (curr != null)
{
// if set contains current node we detect a loop.
if(hs.contains(curr))
{
// Make prev which hold the last node point to null.
System.out.println("Loop Detected at: "+curr.data);
prev.next = null;
return true;
}
// If we see the node for the first time, add it to our set.
else
{
hs.add(curr);
prev = curr;
curr = curr.next;
}
}
return false;
}
public static void main(String[] args)
{
Node head = new Node(12);
head.next = new Node(99);
head.next.next = new Node(37);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(25);
/*Create loop for testing */
head.next.next.next.next.next = head.next;
if (detectandRemoveLoop(head))
{
System.out.print("Linked List after Removing Loop: ");
printList(head);
}
else
System.out.println("No Loop Exists");
}
}
Output:
Loop Detected at: 99 Linked List after Removing Loop: 12 99 37 5 25
Time Complexity: We do a single traversal of the Linked List until we get the loop so the complexity is O(n).
Space Complexity: We use a Hash-Set which at most stores all the nodes of the Linked List, so the space complexity is O(n), for n nodes in list.
Approach 2 (Floyd’s Cycle Detection Algorithm)
- In this approach, we use Floyd’s Cycle Detection Method to detect loop/cycle in our linked list. We use two pointers: One Slow and Another Fast Pointer. We move the slow pointer by one position and the fast pointer by two positions. If they meet at a point then we can say Loop is detected.
- Now after detecting loop we have two cases to consider: 1. If Fast Pointer or Loop is Detected at Head Node. 2. If Fast Pointer is at any other node.
- If the Loop is detected at Head Node or the fast pointer is at head node, we move the Slow pointer until it reaches the node before the head node or the node where loop begins and make its reference to NULL.
- For the 2nd Case, we bring the Slow to position of the head of list. We then continue moving the slow and the fast pointer until slow.next = fast.next . We then make the Fast pointer reference as NULL, thus removing the loop.
Now let us have a quick look at the implementation in java:
import java.util.*;
class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
public class LinkedList
{
static Node head; // head node
// print the linked list elements
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
static void detectAndRemoveLoop(Node head)
{
// if there are no nodes in list.
if(head == null)
return;
Node slow, fast;
slow = fast = head;
while(fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
{
break;
}
}
// Check whether Loop is detected.
if(slow == fast)
{
// Case 1
if(fast == head)
{
while(slow.next != fast)
{
slow = slow.next;
}
System.out.println("Loop Detected at : "+ fast.data);
slow.next = null;
}
// Case 2
else
{
slow = head;
while(slow.next != fast.next)
{
slow = slow.next;
fast = fast.next;
}
System.out.println("Loop Detected at : "+ fast.next.data);
fast.next = null;
}
}
}
public static void main(String[] args)
{
// Creating the Linked List with 5 nodes.
Node head = new Node(12);
head.next = new Node(99);
head.next.next = new Node(37);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(25);
/*Create loop for testing */
head.next.next.next.next.next = head.next;
detectAndRemoveLoop(head);
System.out.print("Linked List after Removing Loop: ");
printList(head);
}
}
Output:
Loop Detected at : 99 Linked List after Removing Loop: 12 99 37 5 25
So we have implemented the code for the same example discussed above. We can see the nodes where the loop is detected and removed. Now let us have a quick look at the Complexities for this approach.
Time Complexity: The time complexity is O(n), since we traverse all nodes of the list before we detect the cycle/loop.
Space Complexity: This approach is efficient in terms of space required which is O(1), since we do not use any auxiliary space instead we just used two pointers.
So that’s it for the article you can try implementing the code with different examples. Let us know your suggestions or doubts in the comment section below.
The post Detect and Remove Loop in a Linked List appeared first on The Crazy Programmer.
from The Crazy Programmer https://ift.tt/3amgBcq
Comments
Post a Comment