Delete duplicates in a linked list

Delete duplicates in a linked list

/*

 * DeleteDupsLinkedList.cpp

 *

 *  Created on: Apr 14, 2012

 *      Author: Kiran Hegde

 */

#include <iostream>

#include <cstdlib>

#include <time.h>

using namespace std;

struct Node {

    int data;

    Node *next;

};

/**

 * Generate a linked list of length "size" containing random numbers from 0 to 9

 */

Node *createLinkedList(int size) {

    srand(time(NULL));

    Node *head = NULL;

    for (int i = 0; i < size; i++) {

        Node *node = new Node;

        node->data = rand() % 10;

        node->next = head;

        head = node;

    }

    return head;

}

void deleteLinkedList(Node *head) {

    while (head != NULL) {

        Node *temp = head;

        head = head->next;

        delete temp;

    }

}

void printLinkedList(Node *head) {

    Node *curr = head;

    while (curr != NULL) {

        cout << curr->data << "-->";

        curr = curr->next;

    }

    cout << "EMPTY" << endl;

}

/**

 *

 */

void deleteDuplicateNodes(Node *head) {

    Node *curr = head;

    //step through the linked list

    while (curr != NULL) {

        Node *firstRunner = curr;

        Node *secondRunner = curr->next;

        // delete all subsequent nodes if they are duplicates

        while (secondRunner != NULL) {

            if (curr->data == secondRunner->data) { // duplicate

                Node *temp = secondRunner;

                firstRunner->next = secondRunner->next;

                secondRunner = secondRunner->next;

                delete temp;

            }

            else {

                firstRunner = firstRunner->next;

                secondRunner = secondRunner->next;

            }

        }

        curr = curr->next;

    }

}

/**

 * Test the function

 */

int main() {

    Node *head = createLinkedList(15);

    cout << "Original List: ";

    printLinkedList(head);

    deleteDuplicateNodes(head);

    cout << "After Deleting Dups: ";

    printLinkedList(head);

    deleteLinkedList(head);

    return 0;

}