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;
};
 
void push(Node*& headRef, int data)
{
    Node* newNode = new Node;
 
    newNode->data = data;
    newNode->next = headRef;
    headRef = newNode;
}
 
void printList(Node* head)
{
    Node* curr = head;
    while (curr)
    {
        cout << curr->data << " —> ";
        curr = curr->next;
    }
 
    cout << "nullptr";
}
 
void removeCycle(Node* head)
{
    Node* prev = nullptr;       
    Node* curr = head;          
 
    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;
 
    Node* head = nullptr;
    for (int i = n; i > 0; i--) {
        push(head, i);
    }
 
    head->next->next->next->next->next = head->next;
 
    removeCycle(head);
    printList(head);
 
    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;
        node.next = head;
        return node;
    }
 
    public static void printList(Node head)
    {
        Node curr = head;
        while (curr != null)
        {
            System.out.print(curr.data + " —> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
 
    public static void removeCycle(Node head)
    {
        Node prev = null;        
        Node curr = head;       
 
        Set<Node> set = new HashSet<>();
 
        while (curr != null)
        {
            if (set.contains(curr))
            {
                prev.next = null;
                return;
            }
 
            set.add(curr);
 
            prev = curr;
            curr = curr.next;
        }
    }
 
    public static void main(String[] args)
    {
        int n = 5;
 
        Node head = null;
        for (int i = n; i > 0; i--) {
            head = push(head, i);
        }
 
        head.next.next.next.next.next = head.next;
 
        removeCycle(head);
        printList(head);
    }
}


Python Implementation:

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
 
def printList(head):
    curr = head
    while curr:
        print(curr.data, end=' —> ')
        curr = curr.next
    print('None')
 
 
def removeCycle(head):
    prev = None        
    curr = head        
 
    s = set()
 
    while curr:
        if curr in s:
            prev.next = None
            return
 
        s.add(curr)
 
        prev = curr
        curr = curr.next
 
 
if __name__ == '__main__':
 
    n = 5
 
    head = None
    for i in reversed(range(1, n + 1)):
        head = Node(i, head)
 
    head.next.next.next.next.next = head.next
 
    removeCycle(head)
    printList(head)


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;
};
void push(Node*& headRef, int data)
{
    Node* newNode = new Node;
 
    newNode->data = data;
    newNode->next = headRef;
    headRef = newNode;
}
 
void printList(Node* head)
{
    Node* curr = head;
    while (curr)
    {
        cout << curr->data << " —> ";
        curr = curr->next;
    }
 
    cout << "nullptr";
}
 
void removeCycle(Node* slow, Node* head)
{
    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;
        }
    }
}
 
Node* identifyCycle(Node* head)
{
    Node *slow = head, *fast = head;
 
    while (fast && fast->next)
    {
        slow = slow->next;
 
        fast = fast->next->next;
 
        if (slow == fast) {
            return slow;
        }
    }
 
    return nullptr;
}
 
int main()
{
    int n = 5;
 
    Node* head = nullptr;
    for (int i = n; i > 0; i--) {
        push(head, i);
    }
 
    head->next->next->next->next->next = head->next;
 
    Node* slow = identifyCycle(head);
    if (slow)
    {
        removeCycle(slow, head);
        printList(head);
    }
    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;
        node.next = head;
        return node;
    }
 
    public static void printList(Node head)
    {
        Node curr = head;
        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;
            }
        }
    }
 
    public static Node identifyCycle(Node head)
    {
        Node slow = head, fast = head;
 
        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;
 
        Node head = null;
        for (int i = n; i > 0; i--) {
            head = push(head, i);
        }
 
        head.next.next.next.next.next = head.next;
 
        Node slow = identifyCycle(head);
 
        if (slow != null)
        {
            removeCycle(slow, head);
            printList(head);
        }
        else {
            System.out.println("No Cycle Found");
        }
    }
}


Python Implementation:

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
def printList(head):
    curr = head
    while curr:
        print(curr.data, end=' —> ')
        curr = curr.next
    print('None')
 
 def removeCycle(slow, head):
 
    curr = head
    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
 
 
def identifyCycle(head):
 
    slow = fast = head
 
    while fast and fast.next:
        slow = slow.next
 
        fast = fast.next.next
 
        if slow == fast:
            return slow
 
    return None
 
 
if __name__ == '__main__':
 
    n = 5
 
    head = None
    for i in reversed(range(1, n + 1)):
        head = Node(i, head)
 
    head.next.next.next.next.next = head.next
 
    slow = identifyCycle(head)
 
    if slow:
        removeCycle(slow, head)
        printList(head)
    else:
        print('No Cycle Found')


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




With this article at Logicmojo, you must have the complete idea of solving Remove the loop in linked list problem.
© 2020 Logicmojo. ALL RIGHTS RESERVED