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
currentNodeandnextNodeof typestruct node.Make
currentNodeto point theheadnode 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
nextNodei.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 pointernextNodei.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);
}
Top comments (0)