1st Algorithm:
Floyd’s Cycle-Finding Algorithm:
Algorithm
This is the fastest method. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.
Working Code For Loop Detection
#include
#include
/* Link list node */
struct node
{
int data;
struct node* next;
};
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int detectloop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;
while(slow_p && fast_p &&
slow_p->next &&
fast_p->next &&
fast_p->next->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
{
printf("Found Loop");
return 1;
}
}
return 0;
}
/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
/* Create a loop for testing */
head->next->next = head;
detectloop(head);
getchar();
}
Time Compelxity O(n)
Space Compelxity O(1)
2nd Algorithm
Brent Algorithm For Loop Detection in Linked List
#include
#include
/* Link list node */
struct node
{
int data;
struct node* next;
};
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int findLoop(struct node* head)
{
if (head == NULL)
return 0;
struct node* slow = head;
struct node* fast = head;
int i = 0;
int k = 1;
while (slow != NULL)
{
slow = slow->next;
i++;
if (slow == fast)
return 1;
if (i == k)
{
fast = slow;
k*= 2;
}
}
return 0;
}
/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
/* Create a loop for testing */
head->next->next = head;
printf(" %d ",findLoop(head));
getchar();
}
Time Compelxity O(n)
Space Compelxity O(1)
Both Above Algos are basically used to detct cycle in Graph.
Algorithm for Removing loop From Linked List
This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.
Working Code For Removing Loop
#include
#include
/* Link list node */
struct Node
{
int value;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->value= new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
void removeloop(struct Node *head)
{
struct Node *p1 = NULL, *p2 = NULL;
while(head)
{
if (p1 == NULL && p2 == NULL)
{
// 1. Two pointers start from head
p1 = head;
p2 = head;
}
else
{
// 2 If two pointers meet, there is a loop
if (p1 == p2)
break;
}
// 3 If pointer reachs the end, there is no loop
if (p2->next == NULL || p2->next->next == NULL)
{
printf("There is no loop in the list.\n");
return ;
}
// 4. One pointer advances one while the other advances two.
p1 = p1->next;
p2 = p2->next->next;
}
// 5. Find out how many nodes in the loop, say k.
unsigned int k = 1;
p2 = p2->next;
while (p1 != p2)
{
p2 = p2->next;
k++;
}
printf("There are %d nodes in the loop of the list.\n", k);
// 6. Reset one pointer to the head, and the other pointer to head + k.
p1 = head;
p2 = head;
for (unsigned int i = 0; i < k; i++) p2 = p2->next;
// 7. Move both pointers at the same pace, they will meet at loop starting node
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
printf("node %d is the loop starting node.\n", p1->value);
// 8. Move one of the pointer till its next node is the loop starting node.
// It's the loop ending node
p2 = p2->next;
while(p2->next != p1)
p2 = p2->next;
printf("node %d is the loop ending node.\n", p2->value);
// 9. Set the next node of the loop ending node to fix the loop
p2->next = NULL;
}
/* Utility function to print a linked list */
void printList(struct Node *head)
{
while(head!=NULL)
{
printf("%d ",head->value);
head=head->next;
}
printf("\n");
}
int main()
{
/* Start with the empty list */
struct Node *head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
head->next->next->next->next->next=head->next->next;
removeloop(head);
printList(head);
printf("\n");
}
Time Compelxity O(n)
Space Compelxity O(1)
Run Here https://ideone.com/wN4tR
You can Have a Look at http://ostermiller.org/find_loop_singly_linked_list.html
Floyd’s Cycle-Finding Algorithm:
Algorithm
This is the fastest method. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.
Working Code For Loop Detection
#include
#include
/* Link list node */
struct node
{
int data;
struct node* next;
};
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int detectloop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;
while(slow_p && fast_p &&
slow_p->next &&
fast_p->next &&
fast_p->next->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
{
printf("Found Loop");
return 1;
}
}
return 0;
}
/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
/* Create a loop for testing */
head->next->next = head;
detectloop(head);
getchar();
}
Time Compelxity O(n)
Space Compelxity O(1)
2nd Algorithm
Brent Algorithm For Loop Detection in Linked List
#include
#include
/* Link list node */
struct node
{
int data;
struct node* next;
};
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int findLoop(struct node* head)
{
if (head == NULL)
return 0;
struct node* slow = head;
struct node* fast = head;
int i = 0;
int k = 1;
while (slow != NULL)
{
slow = slow->next;
i++;
if (slow == fast)
return 1;
if (i == k)
{
fast = slow;
k*= 2;
}
}
return 0;
}
/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
/* Create a loop for testing */
head->next->next = head;
printf(" %d ",findLoop(head));
getchar();
}
Time Compelxity O(n)
Space Compelxity O(1)
Both Above Algos are basically used to detct cycle in Graph.
Algorithm for Removing loop From Linked List
This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.
Working Code For Removing Loop
#include
#include
/* Link list node */
struct Node
{
int value;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->value= new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
void removeloop(struct Node *head)
{
struct Node *p1 = NULL, *p2 = NULL;
while(head)
{
if (p1 == NULL && p2 == NULL)
{
// 1. Two pointers start from head
p1 = head;
p2 = head;
}
else
{
// 2 If two pointers meet, there is a loop
if (p1 == p2)
break;
}
// 3 If pointer reachs the end, there is no loop
if (p2->next == NULL || p2->next->next == NULL)
{
printf("There is no loop in the list.\n");
return ;
}
// 4. One pointer advances one while the other advances two.
p1 = p1->next;
p2 = p2->next->next;
}
// 5. Find out how many nodes in the loop, say k.
unsigned int k = 1;
p2 = p2->next;
while (p1 != p2)
{
p2 = p2->next;
k++;
}
printf("There are %d nodes in the loop of the list.\n", k);
// 6. Reset one pointer to the head, and the other pointer to head + k.
p1 = head;
p2 = head;
for (unsigned int i = 0; i < k; i++) p2 = p2->next;
// 7. Move both pointers at the same pace, they will meet at loop starting node
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
printf("node %d is the loop starting node.\n", p1->value);
// 8. Move one of the pointer till its next node is the loop starting node.
// It's the loop ending node
p2 = p2->next;
while(p2->next != p1)
p2 = p2->next;
printf("node %d is the loop ending node.\n", p2->value);
// 9. Set the next node of the loop ending node to fix the loop
p2->next = NULL;
}
/* Utility function to print a linked list */
void printList(struct Node *head)
{
while(head!=NULL)
{
printf("%d ",head->value);
head=head->next;
}
printf("\n");
}
int main()
{
/* Start with the empty list */
struct Node *head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
head->next->next->next->next->next=head->next->next;
removeloop(head);
printList(head);
printf("\n");
}
Time Compelxity O(n)
Space Compelxity O(1)
Run Here https://ideone.com/wN4tR
