Challenge: remove a loop from a singly linked list if the list has a loop. For example, 1->2->3->4->1 (4 points to the head node 1) should become 1->2->3->4 while 1->2->3->4 should stay the same 1->2->3->4.
Solution: the first task is to determine if our linked list has a loop. If it does, we then need to figure our where the end of the loop is. The reason is that we will set the pointer of the loop's end node to NULL to break the loop. For instance, given the list 1->2->3->1, we must find out whether it has loop. Obviously, that list does have a loop and the loop's end node is 3 (3 points back to head of the loop which is 1). Thus, we need to make node 3 point to NULL so the list doesn't have a loop anymore. The result should be 1->2->3->NULL. Here is the C++ implementation of the algorithm:
#include<iostream>
using namespace std;
struct Node
{
int data;
Node* next;
};
void removeLoop(Node* head)
{
if (head == NULL)
return;
Node* slow = head;
Node* fast = head;
Node* last = NULL;
bool hasLoop = false;
while (fast->next != NULL && fast->next->next != NULL)
{
last = slow;
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
hasLoop = true;
break;
}
}
if (hasLoop)
{
slow = head;
while (slow->next != fast->next)
{
slow = slow->next;
fast = fast->next;
}
if (slow == head && fast == head )
last->next = NULL;
else
fast->next = NULL;
}
}
Explanation: our method takes only the reference to the list's head node as an argument. The first while loop determines if the list has loop. And, the second while loop points the loop's end node to null, terminating the loop:
- If the list is empty (head points to NULL), there is nothing to do so return.
- Next, we need three different pointers. slow will go through the list one node after another. fast moves through the list two nodes at a time, so it goes twice as fast as the slow pointer. And, last refers to the previous node visited by the slow pointer.
- We just have to loop through the list until fast reaches NULL because if the linked list doesn't have loop, fast will reach NULL eventually. Moreover, if the list does have a loop, we'll break out of the while loop immediately.
- As the while loop runs, we check if slow and fast pointer point to the same node. When they do, it means the list has a loop. This is a very common technique to find out if a linked list has loop. Here is a post about that technique if you are not familiar with it.
- As soon as we know that the list has loop, we set the flag hasLoop to true. And then, we break out of the while loop immediately because fast will never reach NULL and the while loop will never end.
- If the list has loop as indicated by the flag hasLoop, we enter the second while loop to remove that the list's loop.
a) First, we set the slow pointer back to the list's head node.
b) Then, we move both the slow and fast pointer one node at a time. They will eventually meet each other because the list still has a loop.
c) We stop the loop right before the pointers meet. That's how we get the reference to the end node of the loop:
d) If the slow and fast pointer both point to the head of the list, then the list is circular, meaning that the end node points back to the head node of the list (ie. 1->2->3->4->1). Thus, we'll get the reference to the end node by using the last pointer. Remember that last is pointing to either the head of the list or the end node of the loop after the first while loop. That's why if slow and fast point at the head, then slow must be pointing at the end node.
e) On the other hand,if the end node is pointing to any node in the list other than the head node (ie. 1->2->3->4->2), then slow and fast is pointing to the end node and last is pointing to the head node. Thus, we use fast pointer instead of last pointer to break the loop.
This algorithm takes O(n) time complexity and O(1) space complexity. It's very efficient!!
