Method3: Detect and remove ll(hashing)
We will use hashing method to hash the address of the nodes.
1. first hash the address of the nodes in the map
2. Traverse the list
3. We find a loop if any element matches
4. Make the next of the pointer point to null
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node{
int key;
struct node* next;
};
node *newnode(int key)
{
node *temp= new node; temp->key= key; temp->next= NULL;
return temp;
} //newnode ends
void printlist(node* head)
{
while(head!=NULL)
{
cout<<head->key<< " ";
head=head->next;
} // while ends
cout<<endl;
} //f ends
void hashandremove(node* head)
{
unordered_map<node*, int>node_map;
node* last= NULL;
while(head!=NULL)
{
if(node_map.find(head)==node_map.end())
{
node_map[head]++; last= head; head=head->next;
} //if ends
else {
last->next= NULL; break;
}
} //while ends
} //f ends
int main() {
node* head= newnode(50);
head->next= head;
head->next->next= newnode(20);
head->next->next = newnode(15);
head->next->next->next = newnode(4);
head->next->next->next->next = newnode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
// printList(head);
hashandremove(head);
printlist(head);
return 0;
}
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home