#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Structure for a node in the singly linked list
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to display the linked list
void displayList(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
printf("Linked List: ");
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// 1. Remove duplicates from a sorted linked list
void removeDuplicatesSorted(struct Node* head) {
if (head == NULL || head->next == NULL) {
return; // No duplicates possible
}
struct Node* current = head;
struct Node* nextNode;
while (current != NULL && current->next != NULL) {
if (current->data == current->next->data) {
nextNode = current->next;
current->next = nextNode->next;
free(nextNode); // Free the duplicate node
} else {
current = current->next;
}
}
printf("Duplicates removed from sorted linked list\n");
}
// 2. Remove duplicates from an unsorted linked list
// Using a simple array-based hash table for demonstration
#define MAX_SIZE 100 // Assuming data values are in range [0, MAX_SIZE)
void removeDuplicatesUnsorted(struct Node** head) {
if (*head == NULL || (*head)->next == NULL) {
return; // No duplicates possible
}
// Initialize hash table (array) to track seen values
bool seen[MAX_SIZE] = {false};
struct Node* current = *head;
struct Node* prev = NULL;
struct Node* temp;
while (current != NULL) {
// If current data is already seen, remove the node
if (seen[current->data]) {
temp = current;
prev->next = current->next;
current = current->next;
free(temp);
} else {
// Mark data as seen and move to next node
seen[current->data] = true;
prev = current;
current = current->next;
}
}
printf("Duplicates removed from unsorted linked list\n");
}
// Main function to test the linked list operations
int main() {
// Test 1: Sorted linked list with duplicates
struct Node* sortedHead = NULL;
insertAtEnd(&sortedHead, 1);
insertAtEnd(&sortedHead, 2);
insertAtEnd(&sortedHead, 2);
insertAtEnd(&sortedHead, 3);
insertAtEnd(&sortedHead, 3);
insertAtEnd(&sortedHead, 4);
printf("Original sorted ");
displayList(sortedHead);
removeDuplicatesSorted(sortedHead);
printf("After removing duplicates: ");
displayList(sortedHead);
// Test 2: Unsorted linked list with duplicates
struct Node* unsortedHead = NULL;
insertAtEnd(&unsortedHead, 1);
insertAtEnd(&unsortedHead, 3);
insertAtEnd(&unsortedHead, 2);
insertAtEnd(&unsortedHead, 3);
insertAtEnd(&unsortedHead, 1);
insertAtEnd(&unsortedHead, 4);
printf("\nOriginal unsorted ");
displayList(unsortedHead);
removeDuplicatesUnsorted(&unsortedHead);
printf("After removing duplicates: ");
displayList(unsortedHead);
return 0;
}
Output:
Comments
Post a Comment