Remove loop from a linked list
Given a linked list of integers, which may contain a cycle, remove the cycle if present.
For example, the following linked list has a cycle in it:
The solution should remove the cycle from the list. The output list should be as follows:
This post provides an overview of some available alternatives to accomplish this – using hashing and Floyd’s cycle detection algorithm.
Related Post:
Detect cycle in a linked list (Floyd’s Cycle Detection Algorithm)
1. Using Hashing
A simple solution is to use hashing. The idea is to traverse the given linked list and insert each encountered node into a hash set. If the node is already present in the HashSet, that means it is seen before and points to the first node in the cycle. To break the cycle, set the next pointer of the previous node to null.
Following is the implementation of the above idea in C++, Java, and Python. The code uses two pointers: curr and prev, where curr is the main pointer running down the list, and prev trails it.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <iostream> #include <unordered_set> using namespace std; // A Linked List Node struct Node { int data; Node* next; }; // Utility function to create a new node with the given data and // pushes it onto the list's front void push(Node*& headRef, int data) { // create a new linked list node from the heap Node* newNode = new Node; newNode->data = data; newNode->next = headRef; headRef = newNode; } // Utility function to print a linked list void printList(Node* head) { Node* curr = head; while (curr) { cout << curr->data << " —> "; curr = curr->next; } cout << "nullptr"; } // Function to identify and remove cycle in a linked list using hashing void removeCycle(Node* head) { Node* prev = nullptr; // previous pointer Node* curr = head; // main pointer // maintain a set to store visited nodes unordered_set<Node*> set; // traverse the list while (curr) { // set the previous pointer to null if the current node is seen before if (set.find(curr) != set.end()) { prev->next = nullptr; return; } // insert the current node into the set set.insert(curr); // update the previous pointer to the current node and // move the main pointer to the next node prev = curr; curr = curr->next; } } int main() { // total number of nodes in the linked list int n = 5; // construct a linked list Node* head = nullptr; for (int i = n; i > 0; i--) { push(head, i); } // insert cycle head->next->next->next->next->next = head->next; removeCycle(head); printList(head); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> nullptr
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
import java.util.HashSet; import java.util.Set; // A Linked List Node class Node { int data; Node next; } class Main { // Utility function to create a new node with the given data and // pushes it onto the list's front public static Node push(Node head, int data) { Node node = new Node(); node.data = data; node.next = head; return node; } // Utility function to print a linked list public static void printList(Node head) { Node curr = head; while (curr != null) { System.out.print(curr.data + " —> "); curr = curr.next; } System.out.println("null"); } // Function to identify and remove cycle in a linked list using hashing public static void removeCycle(Node head) { Node prev = null; // previous pointer Node curr = head; // main pointer // maintain a set to store visited nodes Set<Node> set = new HashSet<>(); // traverse the list while (curr != null) { // set the previous pointer to null if the current node is seen before if (set.contains(curr)) { prev.next = null; return; } // insert the current node into the set set.add(curr); // update the previous pointer to the current node and // move the main pointer to the next node prev = curr; curr = curr.next; } } public static void main(String[] args) { // total number of nodes in the linked list int n = 5; // construct a linked list Node head = null; for (int i = n; i > 0; i--) { head = push(head, i); } // insert cycle head.next.next.next.next.next = head.next; removeCycle(head); printList(head); } } |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# A Linked List Node class Node: def __init__(self, data, next=None): self.data = data self.next = next # Utility function to print a linked list def printList(head): curr = head while curr: print(curr.data, end=' —> ') curr = curr.next print('None') # Function to identify and remove cycle in a linked list using hashing def removeCycle(head): prev = None # previous pointer curr = head # main pointer # maintain a set to store visited nodes s = set() # traverse the list while curr: # `s` previous pointer to None if the current node is seen before if curr in s: prev.next = None return # insert the current node into the set s.add(curr) # update the previous pointer to the current node and # move the main pointer to the next node prev = curr curr = curr.next if __name__ == '__main__': # total number of nodes in the linked list n = 5 # construct a linked list head = None for i in reversed(range(1, n + 1)): head = Node(i, head) # insert cycle head.next.next.next.next.next = head.next removeCycle(head) printList(head) |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> None
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the total number of nodes in the linked list.
2. Using Floyd’s Cycle Detection Algorithm
As seen in the previous post, 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.
First, the idea is to check if a cycle is present in a linked list using Floyd’s cycle detection algorithm and get a pointer to the loop node where fast and slow pointers meet. If a cycle is found, remove it using that loop node. The trick is to find the first node in the linked list that is reachable from the loop node. This node would be the starting node of the loop in the linked list. To break the chain, just set the next pointer of its previous node to null.
Following is the implementation in C++, Java, and Python based on the above idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include <iostream> #include <unordered_set> using namespace std; // A Linked List Node struct Node { int data; Node* next; }; // Utility function to create a new node with the given data and // pushes it onto the list's front void push(Node*& headRef, int data) { // create a new linked list node from the heap Node* newNode = new Node; newNode->data = data; newNode->next = headRef; headRef = newNode; } // Utility function to print a linked list void printList(Node* head) { Node* curr = head; while (curr) { cout << curr->data << " —> "; curr = curr->next; } cout << "nullptr"; } // Function to remove a cycle from a linked list pointed by `head` pointer. // The `slow` pointer points to one of the nodes involved in the cycle void removeCycle(Node* slow, Node* head) { // Do for each node of the linked list for (Node* curr = head; curr != nullptr; curr = curr->next) { // start a pointer `ptr` from the `slow` node and // check if it meets the current node `curr` Node* ptr = slow; while (ptr->next != slow && ptr->next != curr) { ptr = ptr->next; } // If `ptr` meets `curr`, then that means there is a loop, and `curr` points // to the first node of the loop and `ptr` points to the last node if (ptr->next == curr) { // set next pointer of `ptr` to `null` to break the chain ptr->next = nullptr; return; } } } // Function to identify a cycle in a linked list using // Floyd’s cycle detection algorithm Node* identifyCycle(Node* head) { // take two pointers – `slow` and `fast` Node *slow = head, *fast = head; while (fast && fast->next) { // move slow by one pointer slow = slow->next; // move fast by two pointers fast = fast->next->next; // if they meet any node, the linked list contains a cycle if (slow == fast) { return slow; } } // we reach here if the slow and fast pointer does not meet return nullptr; } int main() { // total number of nodes in the linked list int n = 5; // construct a linked list Node* head = nullptr; for (int i = n; i > 0; i--) { push(head, i); } // insert cycle head->next->next->next->next->next = head->next; // first check if a cycle is present in a linked list Node* slow = identifyCycle(head); // if a cycle is found, remove it if (slow) { removeCycle(slow, head); printList(head); } else { cout << "No Cycle Found"; } return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> nullptr
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
// A Linked List Node class Node { int data; Node next; } class Main { // Utility function to create a new node with the given data and // pushes it onto the list's front public static Node push(Node head, int data) { Node node = new Node(); node.data = data; node.next = head; return node; } // Utility function to print a linked list public static void printList(Node head) { Node curr = head; while (curr != null) { System.out.print(curr.data + " —> "); curr = curr.next; } System.out.println("null"); } // Function to remove a cycle from a linked list pointed by `head` pointer. // The `slow` pointer points to one of the nodes involved in the cycle public static void removeCycle(Node slow, Node head) { // Do for each node of the linked list for (Node curr = head; curr != null; curr = curr.next) { // start a pointer `ptr` from the `slow` node and // check if it meets the current node `curr` Node ptr = slow; while (ptr.next != slow && ptr.next != curr) { ptr = ptr.next; } // If `ptr` meets `curr`, then that means there is a loop, and `curr` // points to the first node of the loop and `ptr` points to the last node if (ptr.next == curr) { // set next pointer of `ptr` to `null` to break the chain ptr.next = null; return; } } } // Function to identify a cycle in a linked list using // Floyd’s cycle detection algorithm public static Node identifyCycle(Node head) { // take two pointers – `slow` and `fast` Node slow = head, fast = head; while (fast != null && fast.next != null) { // move slow by one pointer slow = slow.next; // move fast by two pointers fast = fast.next.next; // if they meet any node, the linked list contains a cycle if (slow == fast) { return slow; } } // we reach here if the slow and fast pointer does not meet return null; } public static void main(String[] args) { // total number of nodes in the linked list int n = 5; // construct a linked list Node head = null; for (int i = n; i > 0; i--) { head = push(head, i); } // insert cycle head.next.next.next.next.next = head.next; // first check if a cycle is present in a linked list Node slow = identifyCycle(head); // if a cycle is found, remove it if (slow != null) { removeCycle(slow, head); printList(head); } else { System.out.println("No Cycle Found"); } } } |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
# A Linked List Node class Node: def __init__(self, data, next=None): self.data = data self.next = next # Utility function to print a linked list def printList(head): curr = head while curr: print(curr.data, end=' —> ') curr = curr.next print('None') # Function to remove a cycle from a linked list pointed by `head` pointer. # The `slow` pointer points to one of the nodes involved in the cycle def removeCycle(slow, head): # Do for each node of the linked list curr = head while curr: # start a pointer `ptr` from the `slow` node and # check if it meets the current node `curr` ptr = slow while ptr.next is not slow and ptr.next is not curr: ptr = ptr.next # If `ptr` meets `curr`, then that means there is a loop, and `curr` points # to the first node of the loop and `ptr` points to the last node if ptr.next == curr: # set next pointer of `ptr` to None to break the chain ptr.next = None return curr = curr.next # Function to identify a cycle in a linked list using # Floyd’s cycle detection algorithm def identifyCycle(head): # take two pointers – `slow` and `fast` slow = fast = head while fast and fast.next: # move slow by one pointer slow = slow.next # move fast by two pointers fast = fast.next.next # if they meet any node, the linked list contains a cycle if slow == fast: return slow # we reach here if the slow and fast pointer does not meet return None if __name__ == '__main__': # total number of nodes in the linked list n = 5 # construct a linked list head = None for i in reversed(range(1, n + 1)): head = Node(i, head) # insert cycle head.next.next.next.next.next = head.next # first check if a cycle is present in a linked list slow = identifyCycle(head) # if a cycle is found, remove it if slow: removeCycle(slow, head) printList(head) else: print('No Cycle Found') |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> None
The time complexity of the above approach is O(n2), where n is the total number of nodes in the linked list.
We can easily improve the time complexity to O(n). The idea is to get a pointer to the loop node using Floyd’s cycle detection algorithm and count the total number of nodes in the loop, say k, using that loop node. Then take two pointers – the first pointer pointing to the head of the linked list and the second pointer pointing to the k'th node from the head. If we move both pointers simultaneously, they will eventually meet at the loop starting node. To break the chain, set the next pointer of the last node of the loop to null.
Following is the implementation of the above approach in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <iostream> #include <unordered_set> using namespace std; // A Linked List Node struct Node { int data; Node* next; }; // Utility function to create a new node with the given data and // pushes it onto the list's front void push(Node*& headRef, int data) { // create a new linked list node from the heap Node* newNode = new Node; newNode->data = data; newNode->next = headRef; headRef = newNode; } // Utility function to print a linked list void printList(Node* head) { Node* curr = head; while (curr) { cout << curr->data << " —> "; curr = curr->next; } cout << "nullptr"; } // Function to remove a cycle from a linked list pointed by `head` pointer. // The `slow` pointer points to one of the nodes involved in the cycle void removeCycle(Node* slow, Node* head) { // Find the count of nodes involved in the loop int k = 1; for (Node* ptr = slow; ptr->next != slow; ptr = ptr->next) { k++; } // Get a pointer to k'th node from the head Node* curr = head; for (int i = 0; i < k; i++) { curr = curr->next; } // Simultaneously move the `head` and `curr` pointers at the same speed // until they meet. while (curr != head) { curr = curr->next; head = head->next; } // `curr` points to the last node of the loop while (curr->next != head) { curr = curr->next; } // set the next pointer of `curr` to `null` to break the chain curr->next = nullptr; } // Function to identify a cycle in a linked list using // Floyd’s cycle detection algorithm Node* identifyCycle(Node* head) { // take two pointers – `slow` and `fast` Node *slow = head, *fast = head; while (fast && fast->next) { // move slow by one pointer slow = slow->next; // move fast by two pointers fast = fast->next->next; // if they meet any node, the linked list contains a cycle if (slow == fast) { return slow; } } // we reach here if the slow and fast pointer does not meet return nullptr; } int main() { // total number of nodes in the linked list int n = 5; // construct a linked list Node* head = nullptr; for (int i = n; i > 0; i--) { push(head, i); } // insert cycle Node* lastNode = head->next->next->next->next; lastNode->next = head->next; // first check if a cycle is present in a linked list Node* slow = identifyCycle(head); // if a cycle is found, remove it if (slow) { removeCycle(slow, head); printList(head); } else { cout << "No Cycle Found"; } return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> nullptr
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
// A Linked List Node class Node { int data; Node next; } class Main { // Utility function to create a new node with the given data and // pushes it onto the list's front public static Node push(Node head, int data) { Node node = new Node(); node.data = data; node.next = head; return node; } // Utility function to print a linked list public static void printList(Node head) { Node curr = head; while (curr != null) { System.out.print(curr.data + " —> "); curr = curr.next; } System.out.println("null"); } // Function to remove a cycle from a linked list pointed by `head` pointer. // The `slow` pointer points to one of the nodes involved in the cycle public static void removeCycle(Node slow, Node head) { // Find the count of nodes involved in the loop int k = 1; for (Node ptr = slow; ptr.next != slow; ptr = ptr.next) { k++; } // Get a pointer to k'th node from the head Node curr = head; for (int i = 0; i < k; i++) { curr = curr.next; } // Simultaneously move the `head` and `curr` pointers at the same speed // until they meet. while (curr != head) { curr = curr.next; head = head.next; } // `curr` points to the last node of the loop while (curr.next != head) { curr = curr.next; } // set the next pointer of `curr` to `null` to break the chain curr.next = null; } // Function to identify a cycle in a linked list using // Floyd’s cycle detection algorithm public static Node identifyCycle(Node head) { // take two pointers – `slow` and `fast` Node slow = head, fast = head; while (fast != null && fast.next != null) { // move slow by one pointer slow = slow.next; // move fast by two pointers fast = fast.next.next; // if they meet any node, the linked list contains a cycle if (slow == fast) { return slow; } } // we reach here if the slow and fast pointer does not meet return null; } public static void main(String[] args) { // total number of nodes in the linked list int n = 5; // construct a linked list Node head = null; for (int i = n; i > 0; i--) { head = push(head, i); } // insert cycle head.next.next.next.next.next = head.next; // first check if a cycle is present in a linked list Node slow = identifyCycle(head); // if a cycle is found, remove it if (slow != null) { removeCycle(slow, head); printList(head); } else { System.out.println("No Cycle Found"); } } } |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
# A Linked List Node class Node: def __init__(self, data, next=None): self.data = data self.next = next # Utility function to print a linked list def printList(head): curr = head while curr: print(curr.data, end=' —> ') curr = curr.next print('None') # Function to remove a cycle from a linked list pointed by `head` pointer. # The `slow` pointer points to one of the nodes involved in the cycle def removeCycle(slow, head): # Find the count of nodes involved in the loop k = 1 ptr = slow while ptr.next is not slow: k += 1 ptr = ptr.next # Get a pointer to k'th node from the head curr = head for _ in range(k): curr = curr.next # Simultaneously move the `head` and `curr` pointers at the same speed # until they meet. while curr is not head: curr = curr.next head = head.next # `curr` points to the last node of the loop while curr.next != head: curr = curr.next # set the next pointer of `curr` to `null` to break the chain curr.next = None # Function to identify a cycle in a linked list using # Floyd’s cycle detection algorithm def identifyCycle(head): # take two pointers – `slow` and `fast` slow = fast = head while fast and fast.next: # move slow by one pointer slow = slow.next # move fast by two pointers fast = fast.next.next # if they meet any node, the linked list contains a cycle if slow == fast: return slow # we reach here if the slow and fast pointer does not meet return None if __name__ == '__main__': # total number of nodes in the linked list n = 5 # construct a linked list head = None for i in reversed(range(1, n + 1)): head = Node(i, head) # insert cycle head.next.next.next.next.next = head.next # first check if a cycle is present in a linked list slow = identifyCycle(head) # if a cycle is found, remove it if slow: removeCycle(slow, head) printList(head) else: print('No Cycle Found') |
Output:
1 —> 2 —> 3 —> 4 —> 5 —> None
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)