Remove Duplicate Elements from a Sorted Singly Linked List

Lets remove all duplicate elements from a sorted singly linked list.

For example,

Suppose given linked list contains following elements in given order,

1, 2, 3, 4, 4, 5, 6, 7, 7, 7, 7, 9, 89

After doing this operation on given linked list result should be,

1, 2, 3, 4, 5, 6, 7, 9, 89

Solution:

As list is already sorted therefore all the all similar elements will be together i.e. if element with value 2 is repeated then all instance of elements with value 2 will be together i.e.

1,2,2,2,2,5,6,8

Therefore, we just need to check if there is more than 2 adjacent nodes with same contents or not.
If yes then delete that node and move forward.
[showads ad=inside_post]
Algo Used:

Traverse the whole linked list and always keep track of last visited Node.
During traversal while visiting each node check it contents match with last node’s content
If Data matches
——->Then delete the current node and go to next node
If Data dont matches
——->Then just update the last visited node pointer by making it to point to current node
——->Then go the next node.

Code for the function is as follows,

void removeDuplicatesFromSortedList(node * pNode)
{
	node * pLastNode = NULL;
	while(pNode)
	{
		//Current Node i.e pNode has same value as the last node
		if(pLastNode && pLastNode->value == pNode->value)
		{
			// Yes Current Node i.e pNode has same value as the last node
			// Store the current node i.e. pNode in temporary pointer, so that
			// we can delete it later
			node * pNodeToBeDeleted = pNode;
			// Now make the next pointer of last node to point to current node's next,
			// it will remove the Current element from linked list
			pLastNode->nextPtr = pNode->nextPtr;
			// Now delete the earlier stored temporary node pointer.
			delete pNodeToBeDeleted;
			// Change pLastNode to pNode;
			pNode = pLastNode->nextPtr;
			continue;
		}
		else
		{
			// No Current Node i.e pNode's value don't match with the last node
			// Change pLastNode to pNode;
			pLastNode = pNode;
			// Make pNode to point to next node
			pNode = pNode->nextPtr;
		}

	}
}

complete Code is as follows,

#include <iostream>
/*
 * Node will contain and int variable as value
 * and a node pointer to next Node.
 **/
struct node
{
    int value;
    node * nextPtr;
    node(int val)
    {
        value = val;
        nextPtr = NULL;
    }
};

/*
 * As list is already sorted we just need to check if there is more than 2 adjacent nodes with same contents,
 * if yes then delete one and move forward
 *
 * Algo Used:
 *
 * Traverse the whole linked list and always keep track of last visited Node.
 * During traversal while visiting each node check it contents match with last node's content
 * If Data matches
 * 		Then delete the current node and go to next node
 * If Data dont matches
 * 		Then just update the last visited node pointer by making it to point to current node
 * 		Then go the next node.
 *
 */
void removeDuplicatesFromSortedList(node * pNode)
{
	node * pLastNode = NULL;
	while(pNode)
	{
		//Current Node i.e pNode has same value as the last node
		if(pLastNode && pLastNode->value == pNode->value)
		{
			// Yes Current Node i.e pNode has same value as the last node
			// Store the current node i.e. pNode in temporary pointer, so that
			// we can delete it later
			node * pNodeToBeDeleted = pNode;
			// Now make the next pointer of last node to point to current node's next,
			// it will remove the Current element from linked list
			pLastNode->nextPtr = pNode->nextPtr;
			// Now delete the earlier stored temporary node pointer.
			delete pNodeToBeDeleted;
			// Change pLastNode to pNode;
			pNode = pLastNode->nextPtr;
			continue;
		}
		else
		{
			// No Current Node i.e pNode's value don't match with the last node
			// Change pLastNode to pNode;
			pLastNode = pNode;
			// Make pNode to point to next node
			pNode = pNode->nextPtr;
		}

	}
}
/*
 * Iterate the passed array one by one and create a node
 * for each element and append it in last node's next pointer.
 * Also keep a track of last node created while iteration to
 * update its next pointer in next iteration.
 * Also store the first node created,that we will returned as
 * root node in end.
**/
node * createListFromArray(int * ptr, int arraySize)
{
    node * nodePtr = NULL;
    node * rootNodePtr = NULL;
    node * lastNodePtr = NULL;
    for(int i = 0 ; i < arraySize; i++)
    {
        if(!nodePtr)
        {
            nodePtr = new node(*(ptr+i));
            if(!rootNodePtr)
                rootNodePtr = nodePtr;
            if(lastNodePtr)
                lastNodePtr->nextPtr = nodePtr;
        }
        lastNodePtr = nodePtr;
        nodePtr = nodePtr->nextPtr;
    }
    return rootNodePtr;
}
/*
 * Store the next pointer of passed node as temp variable.
 * Delete the current pointer and pass the earlier stored next pointer
 * to destroyList funtion.
 *
 * If ptr is null it means its the end of linked list, so just return
 * because complete linked list is deleted.
 **/
void destroyList(node * ptr)
{
    if(ptr)
    {
        node * pNext = ptr->nextPtr;
        delete ptr;
        destroyList(pNext);
    }
}
/*
 * Iterate through all nodes and display content
 * of each node untill end of linked list is reached.
 **/
void displayLinkedList(node *ptr)
{
    while(ptr != NULL)
    {
        std::cout<<ptr->value<<" ";
        ptr = ptr->nextPtr;
    }
    std::cout<<std::endl;
}

/*
 * Testing functions.
 **/
int main()
{
    int arr[] = {1,2,3,4,4,5,6,7,7,7,7,9,89};
    node * ptr = createListFromArray(arr, sizeof(arr)/sizeof(int));
    displayLinkedList(ptr);
    removeDuplicatesFromSortedList(ptr);
    displayLinkedList(ptr);
    destroyList(ptr);
    return 0;
}