CareerCup2.1.cpp

CareerCup2.1.cpp

/**
 * Chapter 2
 *
 * 2.1 Write code to remove duplicates from an unsorted linked list. 
 * How would you solve this problem if a temporary buffer is not allowed?
*/
#include <iostream>
#include <unordered_set>  // removeDuplicates() need to remember

using namespace std;

// Define a Node class
class Node {
public:
    int data;
    Node* next;
    
    Node(int num) {
        data = num;
        next = NULL;
    }
};

// Generate a linked-list, return a head pointer
Node* init(int a[], int n) {
    if (n == 0)
        return NULL;
    Node* s = new Node(a[0]);
    //    cout << s->data << endl;
    Node* p = s;
    for (int i = 1; i < n; ++i) {
        Node* t = new Node(a[i]);
        p->next = t;
        p = p->next;
    }
    return s;
}

// Print the linked list
void print(Node* head){
    Node* p = head;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
}

/* Two ways to remove duplicates*/

// 1. Time: O(n), Space: O(n)
// Use unordered_set to record node
void removeDuplicates(Node* head) {
    if (head == NULL)
        return;
    unordered_set<int> record;
    record.insert(head->data);
    Node* p = head;
    unordered_set<int>::const_iterator it;
    while(p->next) {
        it = record.find(p->next->data);
        if ( it == record.end()) {
            record.insert(p->next->data);
            p = p->next;
        }
        else {
            p->next = p->next->next;
        }
    }
}

// 2. Time: O(n^2), Space: O(1)
// The "Runner" Technique
void removeDuplicates1(Node* head) {
    if (head == NULL)
        return;
    Node* p = head;  // iterator
    Node* q = head;  // runner
    while(p) {
        while(q && q->next) {
            if (q->next->data == p->data) {
                // working around current position
                q->next = q->next->next;
            }
            q = q->next;
        }
        p = p->next;
        q = p;
    }
}

// Main Function to test
int main(int argc, char const *argv[])
{
    int a[] = {1, 2, 3, 4, 5, 1};
    int size = sizeof(a) / sizeof(int);
    Node* head = init(a, size);
    cout << "Original linked list: " << endl;
    print(head);
    removeDuplicates(head);
    cout << "\nDuplicated node deleted: " << endl;
    print(head);
    return 0;
}