CareerCup-2.1

Write code to remove duplicates from an unsorted linked list.

FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?

#include <iostream>  
using namespace std;  

// Creating a Linked List:  
struct Node  
{  
    Node(int d):data(d){next = NULL;};  
    int data;  
    Node* next;  
};  

void printNode(Node* head)  
{  
    cout<<"Print:"<<endl;  
    while(head != NULL)  
    {  
        cout<<head->data<<endl;  
        head = head->next;  
    }  
    cout<<"End"<<endl;  
};  

// Deleting a Node from a Singly Linked List  
bool deleteFromPre(Node** head, Node* pre)  
{  
    if(*head == NULL || pre == NULL)  
        return false;  
    Node *p;  
    if((*head) == pre)  
    {  
        p = *head;  
        *head = p->next;   
        delete p;  
        return true;  
    }  
    if(pre->next == NULL)  
        return false;  
    p = pre->next;  
    pre->next = pre->next->next;  
    delete p;  
    return true;  
};  

void removeDuplicates(Node** head)  
{  
    if(head == NULL)  
        return;   
    Node *p, *q;  
    for(p = *head; p != NULL; p = p->next)  
    {  
        for(q = p; q->next != NULL; q = q->next)  
        {  
            if(p->data == q->next->data)  
            {  
                deleteFromPre(head, q);  
                // 这里栽跟头了 删除操作后无法保证q->next不为空   
                if(q->next == NULL)  
                    break;  
            }             
        }  
    }  
};  

int main()  
{  
    Node* head = new Node(2);  
    head->next = new Node(4);  
    head->next->next = new Node(4);  
    printNode(head);  
    removeDuplicates(&head);  
    printNode(head);          
    system("pause");   
};