Exercise 3: Linked List Applications

Exercise 3:

i) Create a program to detect and remove duplicates from a linked list.

// C Program to perform detect and remove duplicates from linked list.

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node* next;
};
void printlist(struct Node* head);
struct Node* Remove(struct Node* head);
void main()
{
    struct Node* head = NULL;
    struct Node* temp = NULL;
    int value;
    char choice;
    do
    {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter the value: ");
        scanf("%d", &value);
        newNode->data = value;
        newNode->next = NULL;
        if (head == NULL)
        {
            head = newNode;
            temp = newNode;
        }
        else
        {
            temp->next = newNode;
            temp = newNode;
        }
        printf("Do you want to enter another data element (y/n): ");
        scanf(" %c", &choice);
    } while (choice == 'y' || choice == 'Y');
    printf("\nLinked list is:\n");
    printlist(head);
    head = Remove(head);
    printf("\nAfter removing the duplicates, the linked list is:\n");
    printlist(head);
}
void printlist(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL)
    {
        printf("%d ---> ", temp->data);
        temp = temp->next;
    }
    printf("NULL");
}
struct Node* Remove(struct Node* head)
{
    struct Node* curr1 = head;
    while (curr1 != NULL)
    {
        struct Node* curr2 = curr1;
        while (curr2->next != NULL)
        {
            if (curr2->next->data == curr1->data)
            {
                struct Node* duplicate = curr2->next;
                curr2->next = curr2->next->next;
                free(duplicate);
            }
            else
            {
                curr2 = curr2->next;
            }
        }
        curr1 = curr1->next;
    }
    return head;
}

---

ii) Implement a linked list to represent polynomials and perform addition.

// C Program for Polynomial representation & addition.

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int coefficient;
    int exponent;
    struct Node* next;
};
// Insert node at end
void insertNode(struct Node** head, int coeff, int exp)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->coefficient = coeff;
    newNode->exponent = exp;
    newNode->next = NULL;
    if (*head == NULL)
    {
        *head = newNode;
    } 
    else
    {
        struct Node* temp = *head;
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = newNode;
    }
}
// Create polynomial
void createPolynomial(struct Node** head)
{
    int n, i, coeff, exp;
    printf("Enter number of terms: ");
    scanf("%d", &n);
    printf("Enter each term (coefficient exponent):\n");
    for (i = 0; i < n; i++) 
    {
        scanf("%d %d", &coeff, &exp);
        insertNode(head, coeff, exp);
    }
}
// Display polynomial
void displayPolynomial(struct Node* head)
{
    while (head != NULL)
    {
        printf("%dx^%d ", head->coefficient, head->exponent);
        head = head->next;
    }
    printf("\n");
}
// Add two polynomials
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2)
{
    struct Node* result = NULL;
    struct Node* temp1 = poly1;
    struct Node* temp2 = poly2;
    while (temp1 != NULL && temp2 != NULL)
    {
        if (temp1->exponent > temp2->exponent)
        {
            insertNode(&result, temp1->coefficient, temp1->exponent);
            temp1 = temp1->next;
        }
        else if (temp1->exponent < temp2->exponent)
        {
            insertNode(&result, temp2->coefficient, temp2->exponent);
            temp2 = temp2->next;
        }
        else
       {
            insertNode(&result, temp1->coefficient + temp2->coefficient,
                       temp1->exponent);
            temp1 = temp1->next;
            temp2 = temp2->next;
        }
    }
   // Remaining terms of poly1
    while (temp1 != NULL)
    {
        insertNode(&result, temp1->coefficient, temp1->exponent);
        temp1 = temp1->next;
    }
    // Remaining terms of poly2
    while (temp2 != NULL)
    {
        insertNode(&result, temp2->coefficient, temp2->exponent);
        temp2 = temp2->next;
    }

    return result;
}
// Main function
int main()
{
    struct Node* poly1 = NULL;
    struct Node* poly2 = NULL;
    struct Node* result = NULL;
    printf("Create Polynomial 1:\n");
    createPolynomial(&poly1);
    printf("Create Polynomial 2:\n");
    createPolynomial(&poly2);
    printf("\nPolynomial 1: ");
    displayPolynomial(poly1);
    printf("Polynomial 2: ");
    displayPolynomial(poly2);
    result = addPolynomials(poly1, poly2);
    printf("\nResultant Polynomial after Addition:\n");
    displayPolynomial(result);
    return 0;
}