Remove Duplicate Elements from a Sorted Singly Linked List

Remove Duplicate Elements from a Sorted Singly Linked List

by

Linked List:

A linked list data structure is made up of a set of nodes that are linked together. Every node stores the data as well as the address of the next node.
You have to start somewhere, so we give the first node’s address a special name called HEAD.

The final node in the linked list can also be marked since its next section points to NULL.

You’ve always played the game Treasure Hunt, where each clue contains details about the next clue. That is how a connected list works.

Examples:

Input:

Linked List :

 5 5 6 6 7 7 7 8 8 9 9 10 11

Output:

5 6 7 8 9 10 11

Remove Repeated Elements from a Sorted Singly Linked List

1)Solution

Since the list is already sorted, all related elements will be grouped together, i.e. if element with value 3 is repeated, all instances of element with value 3 will be grouped together, i.e.

5 6 6 7 7 7 8 9 9 10 11

As a result, we just need to determine if there are more than two adjacent nodes with the same contents.
If yes, remove the node and proceed.

2)Algorithm

Traverse the entire linked list, keeping track of the most recently visited Node.
During the traversal, when visiting each node, compare its contents to the last node’s content.
If the data matches

  • then delete the current node and proceed to the next node.

If the data does not fit

  • simply update the last visited node pointer to point to the current node.
  • Then proceed to the next node.

3)Implementation

Below is the implementation:

#include <iostream>
using namespace std;
/*
 Node will have an int variable as its value as well as a
 node pointer(link) to the next Node.
 */
struct node {
    int value;
    node* link;
    node(int intval)
    {
        value = intval;
        link = NULL;
    }
};

void removeRepeatedElementsFromSortedLinkedList(
    node* current_node)
{
    node* lastNode = NULL;
    while (current_node) {
        // The new node, i.e. current node, has the same
        // value as the previous node.
        if (lastNode
            && lastNode->value == current_node->value) {
            /* Yes, the new node, i.e. current node, has the
           same value as the previous node. Keep the current
           node, current node, in a temporary pointer so
           that we can erase it later.*/
            node* nodeToBeDeleted = current_node;
            /*  Let the last node's next pointer point to
            the current node's next this will delete the
            Current entity from the linked list.*/
            lastNode->link = current_node->link;
            // Delete the previously saved temporary node
            // pointer.
            delete nodeToBeDeleted;
            // changing lastnode to cuurent node
            current_node = lastNode->link;
            continue;
        }
        else {
            /*There is no current node, i.e. the value of
          current node does not match the value of the
          previous node. Lastnode should be changed to
          current node
            */

            lastNode = current_node;
            // make the currentnode to point to next node
            current_node = current_node->link;
        }
    }
}
/*
 Iterate through the passed array one by one, creating a
node for each element and appending it to the last node's
next pointer. Keep track of the last node generated during
iteration in order to update its next pointer in the next
iteration. Also, save the first node generated, which will
be returned as the root node at the end.
 */
node* createList(int* pointer, int sizeArr)
{
    node* nodePointer = NULL;
    node* rootNodePointer = NULL;
    node* lastNodePointer = NULL;
    for (int i = 0; i < sizeArr; i++) {
        if (!nodePointer) {
            nodePointer = new node(*(pointer + i));
            if (!rootNodePointer)
                rootNodePointer = nodePointer;
            if (lastNodePointer)
                lastNodePointer->link = nodePointer;
        }
        lastNodePointer = nodePointer;
        nodePointer = nodePointer->link;
    }
    return rootNodePointer;
}
/*
 As a temp variable, save the next pointer of the passed
node. Remove the current pointer and transfer the previously
saved next pointer to the destroyList feature.

If ptr is null, it means the linked list has reached its
end  simply return since the entire linked list has been
removed.
 */
void destroyLinkedList(node* pointer)
{
    if (pointer) {
        node* ptrNext = pointer->link;
        delete pointer;
        destroyLinkedList(ptrNext);
    }
}
/*
 Iterate through all nodes,
 displaying the content of each node until the linked list
 reaches its end.
 */
void displayLinkedList(node* pointer)
{
    while (pointer != NULL) {
        cout << pointer->value << " ";
        pointer = pointer->link;
    }
    cout << endl;
}
int main()
{
    int intarray[]
        = { 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 10, 11 };
    node* pointer = createList(intarray, sizeof(intarray)
                                             / sizeof(int));
    // printing the linked list
    displayLinkedList(pointer);
    removeRepeatedElementsFromSortedLinkedList(pointer);
    displayLinkedList(pointer);
    destroyLinkedList(pointer);
    return 0;
}

Output:

5 5 6 6 7 7 7 8 8 9 9 10 11 
5 6 7 8 9 10 11

Related Programs: