Given a circular linked list, implement an algorithm which returns node at the beginning of the loop and cut it off.
#include <iostream>
using namespace std;
typedef struct linked_list
{
int data;
struct linked_list *next;
}Linked_list;
Linked_list *create_node(int d)
{
Linked_list *l = new Linked_list;
if(NULL != l){
l->data = d;
l->next = NULL;
}
return l;
}
bool add_node(Linked_list **h, Linked_list *l)
{
Linked_list *runner;
if(*h == NULL){
*h = l;
return true;
}
runner = *h;
while(runner->next != NULL){
runner = runner->next;
}
runner->next = l;
return true;
}
bool find_loop_start(Linked_list *h, Linked_list **start)
{
int first_meet = 0;
// if link is none
if(h == NULL)
return false;
// if loop linked-list with 1 element
if(h->next == NULL){
return false;
}
if(h->next->next == NULL){
return false;
}
Linked_list *slow = h;
Linked_list *fast = h->next;
while(slow != NULL || fast != NULL){
if(slow->next == NULL)
return false;
if(fast->next == NULL)
return false;
if(fast->next->next == NULL)
return false;
if(fast == slow){
break;
}
slow = slow->next;
fast = fast->next->next;
}
if(fast != slow)
return false;
Linked_list *current = h;
Linked_list *runner = slow; // in loop;
if(slow->next == slow){
*start = slow;
return true;
}
while(current != NULL){
runner = slow;
while(runner->next != slow){
if(runner == current){
*start = runner;
break;
}
runner = runner->next;
}
if(runner == current)
break;
current = current->next;
}
// cut the loop
runner = current;
while(runner->next != current){
runner = runner->next;
}
runner->next = NULL;
return true;
}
int main(int argc, char* argv[])
{
Linked_list *head = NULL;
Linked_list *loop_start = NULL;
Linked_list *loop_end = NULL;
Linked_list *l;
int i;
for(i = 0; i < 20; i++){
l = create_node(i);
add_node(&head, l);
}
loop_start = create_node(100);
add_node(&head, loop_start);
for(i = 20; i < 30; i++){
l = create_node(i);
add_node(&head, l);
}
loop_end = create_node(30);
loop_end->next = loop_start;
add_node(&head, loop_end);
cout << "before dection" << endl;
l = head;
i = 0;
while( l!= NULL){
cout << "address: " << l << "data: " << l->data << endl;
i ++;
if(i > 35)
break;
l = l->next;
}
Linked_list *start;
if(find_loop_start(head, &start)){
cout << head << " is a looped linked-list" << endl;
cout << start << "datat: " << start->data << "is the loop start" << endl;
}
else{
cout << head << " is NOT a looped linked-list" << endl;
}
cout << "after cut loop" << endl;
l = head;
while(l != NULL){
cout << l->data << endl;
l = l->next;
}
return 0;
}