0

For instance if the link list is like :

1->2->3->4->5->6->7->8->9->4

We can find the loop using Floyd Cycle Algorithm but how to remove the loop in such cases?.

Improve this question
3
  • The algorithm is nothing to do with removing loops... Commented Jul 5, 2014 at 9:53
  • but if we want to remove the loop from the above linked list then how can be do so? Commented Jul 5, 2014 at 10:27
  • Looking at the algorithm on wikipedia, it detects the position of the loop. Look for the second instance of this link, and remove it from the list. Commented Jul 5, 2014 at 11:08

2 Answers 2

Reset to default
2 
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.

e.g. of your case: 1->2->3->4->5->6->7->8->9->4

1) Loop verified by Floyd's cycle detection algo. 2) count of nodes in loop = 6 3) head->1, p->7 (6th node from head) 4) Loop while head!=p head=head->next and p=p->next. Both will meet at node 4 5) p=p->next Loop while(p->next!=head) p=p->next; Put p->next=NULL after termination of above loop. Your new list will be 1->2->3->4->5->6->7->8->9->NULL
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

-1

Assuming cycle is present in the linked list, Using Hashtable or map in c++.

 map<struct node*, int> m; m[head]++; while (head->next != NULL) { if (m.find(head->next) != m.end()) { head->next = NULL; break; } else m[head->next]++; head = head->next; }
Improve this answer

1 Comment

Removed, the second approach.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.