Delete duplicate nodes from sorted linked list in c
C program for Delete duplicate nodes from sorted linked list. Here problem description and explanation.
/*
C program for
Delete duplicate nodes in sorted linked list
*/
#include <stdio.h>
#include <stdlib.h>
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *)
malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Handles the request of adding new node at end of linked list
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *)
malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow to Create LinkNode\n");
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
if (sll->head == NULL)
{
sll->head = node;
}
else
{
sll->tail->next = node;
}
sll->tail = node;
}
// Display linked list element
void display(struct LinkNode *node)
{
if (node == NULL)
{
return;
}
struct LinkNode *temp = node;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Remove the duplicate nodes from sorted singly linked list
void deleteDuplicate(struct SingleLL *sll)
{
if (sll->head == NULL)
{
return;
}
else
{
// Auxiliary variables
struct LinkNode *temp = sll->head->next;
struct LinkNode *current = sll->head;
struct LinkNode *hold = NULL;
// Find and remove duplicate
while (temp != NULL)
{
// Check duplicate node
if (current->data == temp->data)
{
// When node key are same
hold = temp;
}
else
{
// When node key are not same
current = temp;
}
// Visit to next node
temp = temp->next;
if (hold != NULL)
{
// Modified link value
current->next = temp;
// Remove nodes
free(hold);
hold = NULL;
}
else
{
sll->tail = current;
}
}
}
}
int main(int argc, char
const *argv[])
{
struct SingleLL *sll = newLinkedList();
// Sorted Linked list node
addNode(sll, 1);
addNode(sll, 1);
addNode(sll, 2);
addNode(sll, 3);
addNode(sll, 4);
addNode(sll, 4);
addNode(sll, 4);
addNode(sll, 5);
addNode(sll, 6);
addNode(sll, 7);
printf(" Before Delete \n");
display(sll->head);
deleteDuplicate(sll);
printf(" After Delete \n");
display(sll->head);
return 0;
}
Output
Before Delete
1 → 1 → 2 → 3 → 4 → 4 → 4 → 5 → 6 → 7 → NULL
After Delete
1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment