Remove Duplicates From Sorted Linked List.

#c #linkedlist #beginners

Suppose you are given a sorted linked list, you need to traverse a linked list, remove the duplicates from the list if exists and then print the resultant sorted linked list.

Example 1 :

Input : Linked List : 1, 2, 2, 3, 3, 4, 5
Output : Linked List after removing duplicates : 1, 2, 3, 4, 5

Example 2 :

Input : Linked List : 5, 5, 6, 7, 8, 8
Output : Linked List after removing duplicates : 5, 6, 7, 8

Steps :

Declare two pointers currentNode and nextNode of type struct node.
Make currentNode to point the head node of the linked list.
Keep iterating through the linked list until last node is reached.
Compare the data of current node with the data of next node.
If they are equal, then detach one of the node(which is considered as duplicate) from the list by saving its neighbour node's address into pointer nextNode i.e., nextNode = currentNode->next->next. Then break the link between current node and the duplicate node and attach the current node to the node pointing to by pointer nextNode i.e., currentNode->next = nextNode.
If not, then continue traversing the linked list.
Finally, print the linked list.

C program that removes the duplicates from sorted linked list :

*******************************************************************************/
#include <stdio.h>
#include <stdlib.h> 

struct node
{
    int data;
    struct node * next;
};

void displayLL(struct node * head)
{
    struct node * temp;
    temp = head;
    temp=head;
    while(temp!=0)
    {
       printf("%d ",temp->data);
       temp = temp->next;
    }
}

void removeDup(struct node *head)
{
    struct node *currentNode = head;
    struct node *nextNode;

    while(currentNode != NULL && currentNode->next != NULL)
  {
       if(currentNode->data == currentNode->next->data )
       {   
           nextNode = currentNode->next->next;
        if(nextNode == NULL)
           {
             currentNode->next = NULL;
             break;
           }
           currentNode->next = nextNode;
       }   
       if(currentNode->data != currentNode->next->data)
       {
           currentNode = currentNode->next;
       }
   }
    printf("\n--------------------------------\n");
    printf("Linked List after removing duplicates : ");
    displayLL(head);
}

int main()
{
   struct node *head = 0, *newnode, *temp; 
   int n, choice, newdata;

// Create Linked List // 

   printf("Enter the number of nodes in the list : ");
   scanf("%d", &n);
   for(int i = 1; i<=n; i++)
   {
     newnode = (struct node *)malloc(sizeof(struct node));
     printf("Enter the data%d : ", i);
     scanf("%d", &newnode->data);
     newnode->next = 0;
     if(head == 0)
     {
        head = temp = newnode;
     } 
     else
       { 
        temp->next = newnode;
        temp = newnode;
       }
    }
   printf("--------------------------------\n");
   printf("Linked list : ");

   displayLL(head);
   removeDup(head);
}