Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Write a function, detectAndRemoveLoop(), that checks if a given list contains loops, and if it does, drops the loop and returns true. If the list does not contain loops, return false. The following figure shows a linked list with loops. DetectAndRemoveLoop () must change the list below to 1->2->3->4->5->NULL.

We also recommend reading the following posts as a prerequisite for the solution discussed here. Write a C function to detect a loop in a linked list. Before attempting to delete a loop, we must detect it. The techniques discussed in the above post can be used to detect loops. To remove the loop, all we need to do is get a pointer to the last node of the loop. For example, the node with a median value of 5 in the figure above. Once we have a pointer to the last node, we can set the next node of this node to NULL and the loop is gone. We can easily use hashing or access node techniques (discussed in the above post) to get a pointer to the last node. The idea is simple: the next first node that has been accessed (or hashed) is the last node. We can also use the Freudian cycle detection algorithm to detect and delete cycles. In The Freudian algorithm, slow and fast Pointers meet at the loop node. We can use the loop node to remove the loop. When using the Floyd algorithm for loop detection, there are two different ways to eliminate loops.

We know that the Freudian loop detection algorithm stops when the fast and slow Pointers meet at a common point. We also know that this common point is one of the loop nodes (2 or 3 or 4 or 5 in the figure above). Store the address of this in a pointer variable such as ptr2. Then, starting at the head of the list, check each node to see if it is reachable from PTR2. Every time we find a reachable node, we know that this node is the start of the loop in the linked list, and we can get a pointer to the previous node of this node.

Output:

Linked List after removing loop 
50 20 15 4 10
Copy the code

Method 2 (Better Solution)

  1. The method also relies on Floyd’s Cycle detection algorithm.
  2. The Floyd cycle detection algorithm is used to detect the cycle and obtain the pointer to the cycle node.
  3. Count the number of nodes in the loop. Let’s make the count k.
  4. Fix one pointer to the head and the other to the KTH node of the head.
  5. Move two Pointers at the same speed and they will meet at the start of the loop.
  6. Gets a pointer to the last node of the loop and sets its next node to NULL.
#include <bits/stdc++.h>
using namespace std;

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

void removeLoop(struct Node*, struct Node*);

int detectAndRemoveLoop(struct Node* list)
{
	struct Node *slow_p = list, *fast_p = list;

	while (slow_p && fast_p && fast_p->next) {
		slow_p = slow_p->next;
		fast_p = fast_p->next->next;

		if (slow_p == fast_p) {
			removeLoop(slow_p, list);

			/* Return 1 to indicate that loop is found */
			return 1; }}return 0;
}

void removeLoop(struct Node* loop_node, struct Node* head)
{
	struct Node* ptr1 = loop_node;
	struct Node* ptr2 = loop_node;

	unsigned int k = 1, i;
	while(ptr1->next ! = ptr2) { ptr1 = ptr1->next; k++; } ptr1 = head; ptr2 = head;for (i = 0; i < k; i++)
		ptr2 = ptr2->next;

	while(ptr2 ! = ptr1) { ptr1 = ptr1->next; ptr2 = ptr2->next; }while(ptr2->next ! = ptr1) ptr2 = ptr2->next; ptr2->next =NULL;
}

void printList(struct Node* node)
{
	while(node ! =NULL) {
		cout << node->data << ""; node = node->next; }}struct Node* newNode(int key)
{
	struct Node* temp = new Node(a); temp->data = key; temp->next =NULL;
	return temp;
}

int main(a)
{
	struct Node* head = newNode(50);
	head->next = newNode(20);
	head->next->next = newNode(15);
	head->next->next->next = newNode(4);
	head->next->next->next->next = newNode(10);

	head->next->next->next->next->next = head->next->next;

	detectAndRemoveLoop(head);

	cout << "Linked List after removing loop \n";
	printList(head);
	return 0;
}
Copy the code

Output:

Linked List after removing loop 
50 20 15 4 10 
Copy the code

🥇 past quality articles

Singly linked list data structure of the chain table from the introduction of | first set of singly linked list data structure linked list and array | second singly linked list data structure of chain table insert | | delete nodes of the third set of singly linked list data structure of the fourth set of singly linked list data structure to delete a given location linked list node | the fifth set Singly linked list data structure of the check method of array and list | singly linked list data structure of the set of 6-1 check method of array and list | set 6-2 singly linked list data structure of the length of the chain table lookup (iteration and recursion) | 7 sets of singly linked list data structure of switching nodes in the list without exchanging data | 8 sets Singly linked list data structure of the inversion list | 9 sets of singly linked list data structure of merging two sorted lists | 10 sets of singly linked list data structure of the list of merge sort | 11 sets of singly linked list data structure with the size of a given set of inversion list | 12 sets

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.