QSN。給定一個 N 個節點的未排序鏈表。任務是從這個未排序的鏈表中洗掉重復的元素。當一個值出現在多個節點中時，首先出現的節點應該保留，其他所有重復的節點都將被洗掉。我試圖自己撰寫這段代碼，但在這段代碼之后顯示了我附加的錯誤。
class Solution
{public: Node * removeDuplicates( Node *head)
{ Node *curr = head;
Node *temp = head->next;
while(curr!=NULL)
{
temp = curr->next;
while(temp!=NULL)
{
if(curr->data == temp->data)
{
curr->next = temp->next;
temp = curr->next;
}
else
temp = temp->next;
}
curr = curr->next;
}
return head;
}
};
對于下面給出的某些測驗用例，它沒有運行：
輸入：1
6
2 2 2 3 4 2
你的輸出：2
預期產出：2 3 4
uj5u.com熱心網友回復：
我們可以使用unorderd_set來維護資料并使用prev 指標來存盤前一個節點的參考。如果資料不在集合中，我們將遍歷鏈表，如果資料被存盤，我們會將其添加到集合中，然后我們將使前一個節點指向當前筆記的下一個，這樣我們就可以洗掉重復項。
#include <bits/stdc .h>
using namespace std;
class Solution{
public: Node * removeDuplicates( Node *head) {
Node *curr = head;
Node *temp = head->next;
/*while(curr!=NULL){
temp = curr->next;
while(temp!=NULL){
if(curr->data == temp->data){
curr->next = temp->next;
temp = curr->next;
}else temp = temp->next;
}
curr = curr->next;
}
return head;
*/
Node *prev;
unordered_set<int> us;//To Store unique data
while (curr != NULL){
if( us.find(curr->data) == us.end()){//if not found in the set
prev=curr;
us.insert(curr->data);// adding to the set
curr=curr->next;//point to next one
}else{//found earlier in the set
prev->next=curr->next;
curr=curr->next;
}
}
return head;
}
};
完整的程式在哪里洗掉重復節點而不使用集合記住這里我們使用前一個節點如果遇到的資料是重復的那么我們將使前一個節點指向當前節點的下一個節點這樣我們可以洗掉當前節點（重復一）。
代碼：
#include <bits/stdc .h>
using namespace std;
class Node{
public :
Node * next;
int data;
Node(){
next=NULL;
data=0;
}
Node(int data){
this->data=data;
next=NULL;
}
};
//class Solution{
// public:
//
//};
//Removes Duplicates using an ordered_set
Node * removeDuplicates( Node *head) {
Node *curr = head;
Node *temp = head->next;
/*while(curr!=NULL){
temp = curr->next;
while(temp!=NULL){
if(curr->data == temp->data){
curr->next = temp->next;
temp = curr->next;
}else temp = temp->next;
}
curr = curr->next;
}
return head;
*/
Node *prev;
unordered_set<int> us;//To Store unique data
while (curr != NULL){
if( us.find(curr->data) == us.end()){//if not found in the set
prev=curr;
us.insert(curr->data);// adding to the set
curr=curr->next;//point to next one
}else{//found earlier in the set
prev->next=curr->next;
curr=curr->next;
}
}
return head;
}
//Removes duplicates with out using list
//Here maintaining a prev node will do the trick
Node * deleteDuplicates(Node * head){
Node * curr = head;
//Iterating all over the linked nodes
while ( curr != NULL ){
Node * temp=curr->next;
Node * prev = curr;
while(temp != NULL){
//if this data is already there in list
if(temp->data == curr->data){
prev->next=temp->next;
}else{
prev=temp;//notice our prev is temp when this data is not equal to curr->data
}
temp=temp->next;
}
curr=curr->next;
}
return head;
}
//add a node at the end
void addNodeAtEnd(Node * head,int data){
Node * temp=head;
while (temp->next != NULL)
temp=temp->next;
temp->next=new Node(data);
}
//displays all nodes
void printAllNodes(Node * head){
Node * temp=head;
while (temp != NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main(){
Node * head=new Node(5);
addNodeAtEnd(head,20);
addNodeAtEnd(head,30);
addNodeAtEnd(head,30);
addNodeAtEnd(head,30);
addNodeAtEnd(head,5);
addNodeAtEnd(head,30);
addNodeAtEnd(head,40);
addNodeAtEnd(head,50);
addNodeAtEnd(head,30);
addNodeAtEnd(head,50);
addNodeAtEnd(head,20);
printAllNodes(head);
//head=removeDuplicates(head);
head=deleteDuplicates(head);
//displaying all the nodes after removing duplicates
printAllNodes(head);
return 0;
}
輸出 ：
$ g Node.cpp && ./a.out
5 20 30 30 30 5 30 40 50 30 50 20
5 20 30 40 50
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/419681.html
標籤：
上一篇：如何在網格內制作方形跟隨滑鼠游標