# Remove Loop in Linked List

Back to home
Logicmojo - Updated Aug 28, 2021

## Problem Statement: Remove Loop in Linked List

Given a Linked list, find out whether it contains a loop or not. If it does, then remove the loop and make the last node point to NULL.

In a linked list, a loop is encountered when the last node points to any node in the linked list instead of pointing to NULL.

We have presented two approaches to remove the loop in linked list:

• Using HashSet
• Using Floyd’s Cycle Detection Algorithm

### Approach 1: Using HashSet

The use of hashing is a straightforward method. The goal is to walk through the given linked list and add each node to a hash set. If the node is already in the HashSet, it signifies it has been seen previously and points to the cycle's first node. Set the previous node's next pointer to null to stop the loop.

C++ Implementation:

```#include <iostream>
#include <unordered_set>
using namespace std;

struct Node
{
int data;
Node* next;
};

{
Node* newNode = new Node;

newNode->data = data;
}

{
while (curr)
{
cout << curr->data << " —> ";
curr = curr->next;
}

cout << "nullptr";
}

{
Node* prev = nullptr;

unordered_set<Node*> set;

while (curr)
{
if (set.find(curr) != set.end())
{
prev->next = nullptr;
return;
}

set.insert(curr);

prev = curr;
curr = curr->next;
}
}

int main()
{
int n = 5;

for (int i = n; i > 0; i--) {
}

return 0;
}
```

Java Implementation:

```import java.util.HashSet;
import java.util.Set;

class Node
{
int data;
Node next;
}

class Main
{
public static Node push(Node head, int data)
{
Node node = new Node();
node.data = data;
return node;
}

{
while (curr != null)
{
System.out.print(curr.data + " —> ");
curr = curr.next;
}
System.out.println("null");
}

{
Node prev = null;

Set<Node> set = new HashSet<>();

while (curr != null)
{
if (set.contains(curr))
{
prev.next = null;
return;
}

prev = curr;
curr = curr.next;
}
}

public static void main(String[] args)
{
int n = 5;

for (int i = n; i > 0; i--) {
}

}
}
```

Python Implementation:

```class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next

while curr:
print(curr.data, end=' —> ')
curr = curr.next
print('None')

prev = None

s = set()

while curr:
if curr in s:
prev.next = None
return

prev = curr
curr = curr.next

if __name__ == '__main__':

n = 5

for i in reversed(range(1, n + 1)):

```

Time Complexity: O(N) where N is the number of nodes of the linked list.

Space Complexity: O(N), as HashSet is used

### Approach 2: Using Floyd’s Cycle Detection Algorithm

Floyd’s cycle detection algorithm maintains two pointers where the first pointer moves at twice the speed of the second pointer. If both pointers meet at some point, a cycle is found in the list.

The first step is to use Floyd's cycle detection algorithm to see if a cycle exists in a linked list and then retrieve a pointer to the loop node where the fast and slow pointers meet. If a cycle is discovered, use that loop node to break it. The challenge is to locate the first linked list node that can be reached from the loop node. The initial node of the loop in the linked list would be this node. To break the chain, simply set the previous node's next pointer to null.

Algorithm

1. Set two pointers to the head of the linked list, one fast and one slow.

2. Traverse through the linked list until the fast pointer doesn’t reach the end of the linked list.

3. If the fast pointer reaches the end of the linked list, it signifies there are no cycles.

4. Else, move the slow pointer by one node i.e. slow = slow -> next and fast pointer by two nodes i.e. fast = fast -> next -> next.

5. At any point, if the fast and the slow pointers point to the same node, set node-> next = NULL and return True as a loop has been detected.

C++ Implementation:

```#include <iostream>
#include <unordered_set>
using namespace std;

struct Node
{
int data;
Node* next;
};
{
Node* newNode = new Node;

newNode->data = data;
}

{
while (curr)
{
cout << curr->data << " —> ";
curr = curr->next;
}

cout << "nullptr";
}

{
for (Node* curr = head; curr != nullptr; curr = curr->next)
{
Node* ptr = slow;
while (ptr->next != slow && ptr->next != curr) {
ptr = ptr->next;
}

if (ptr->next == curr)
{
ptr->next = nullptr;
return;
}
}
}

{

while (fast && fast->next)
{
slow = slow->next;

fast = fast->next->next;

if (slow == fast) {
return slow;
}
}

return nullptr;
}

int main()
{
int n = 5;

for (int i = n; i > 0; i--) {
}

if (slow)
{
}
else {
cout << "No Cycle Found";
}

return 0;
}
```

Java Implementation:

```class Node
{
int data;
Node next;
}

class Main
{
public static Node push(Node head, int data)
{
Node node = new Node();
node.data = data;
return node;
}

{
while (curr != null)
{
System.out.print(curr.data + " —> ");
curr = curr.next;
}
System.out.println("null");
}

public static void removeCycle(Node slow, Node head)
{
for (Node curr = head; curr != null; curr = curr.next)
{
Node ptr = slow;
while (ptr.next != slow && ptr.next != curr) {
ptr = ptr.next;
}

if (ptr.next == curr)
{
ptr.next = null;
return;
}
}
}

{

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

fast = fast.next.next;

if (slow == fast) {
return slow;
}
}

return null;
}

public static void main(String[] args)
{
int n = 5;

for (int i = n; i > 0; i--) {
}

if (slow != null)
{
}
else {
System.out.println("No Cycle Found");
}
}
}
```

Python Implementation:

```class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next

while curr:
print(curr.data, end=' —> ')
curr = curr.next
print('None')

while curr:

ptr = slow
while ptr.next is not slow and ptr.next is not curr:
ptr = ptr.next

if ptr.next == curr:
ptr.next = None
return

curr = curr.next

while fast and fast.next:
slow = slow.next

fast = fast.next.next

if slow == fast:
return slow

return None

if __name__ == '__main__':

n = 5

for i in reversed(range(1, n + 1)):

if slow: