CODEWITHSUNDEEP
calgorithmdata-structureslinked-listfloyd-cycle-finding
Vipul
Vipul

Reputation: 576

How the loops are removed from link list

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?.

Upvotes: 0

Views: 594

Answers (2)

Nitish Jain
Nitish Jain

Reputation: 734

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;
           }

Upvotes: -1

Ayush
Ayush

Reputation: 2608

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

Upvotes: 2

Related Questions