Overview of the Project:

This is a C programming project that implements a linked list data structure. The project includes functions to insert nodes at the beginning, end, and in between in a sorted linked list in ascending order, as well as functions to find the union and intersection of two linked lists. The program takes inputs for the number of elements to be inserted and the values for each element in two separate linked lists and then outputs the union and intersection of these linked lists.

#include<stdio.h>//standard input output
#include<stdlib.h>// for accessing malloc function

struct node *getnode();//Function to get a new node
void InsBeg (struct node **start, int x);//function to enter the value at the beginning
void InsEnd (struct node **start, int x);//function to enter the value at the end
void InsAft (struct node **p, int x);//function to enter the value in between
void InsInOrder (struct node **start, int x);//function to enter the value in order
void Traverse (struct node **start);//traverse the list
void Union(struct node *list1, struct node *list2);//make union
void Intersection(struct node *list1, struct node *list2);//make intersection


// Definition of the node structure
struct node
{
   int data; // data to be stored
   struct node *next; // pointer to the next node which is self referencing
};

/* main function */
int main () {

  /* declare pointers for linked list 1 and linked list 2 */
  struct node *list1, *list2;

  /* initialize the linked lists to be empty */
  list1 = NULL;
  list2 = NULL;

  int n, x;

  /* insert elements into linked list 1 */
  printf("Enter the number of elements to insert into linked list 1: ");
  fflush(stdout);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
  printf("Enter element %d: ", i+1);
  fflush(stdout);
  scanf("%d", &x);
  InsInOrder (&list1, x);
  }

  /* print linked list 1 */
  printf ("Linked List 1 is: ");
  Traverse (&list1);
  printf ("\n");

  /* insert elements into linked list 2 */
  printf("Enter the number of elements to insert into linked list 2: ");
  fflush(stdout);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
  printf("Enter element %d: ", i+1);
  fflush(stdout);
  scanf("%d", &x);
  InsInOrder (&list2, x);
  }

  /* print linked list 2 */
  printf ("Linked List 2 is: ");
  Traverse (&list2);
  printf ("\n");

  /* find union of linked list 1 and linked list 2 */
  printf ("Union of Linked List 1 and Linked List 2 is: ");
  Union (list1, list2);
  printf ("\n");

  /* find intersection of linked list 1 and linked list 2 */
  printf ("Intersection of Linked List 1 and Linked List 2 is: ");
  Intersection (list1, list2);
  printf ("\n");



  /* return 0 to indicate successful completion of the program */
  return 0;
}

// Function to get a new node
struct node *getnode()
{
   struct node *p;//head node
   p = (struct node *) malloc (sizeof (struct node));//get dynamic heap memory of nodes to store the data
   return p;
}

// Function to insert a node at the beginning of the linked list
void InsBeg (struct node **start, int x)
{
   struct node *p = getnode(); // get a new node
   p->data = x; // store the data in the node
   p->next = (*start); // make the new node point to the current first node
   (*start) = p; // make the new node the first node
}

// Function to insert a node at the end of the linked list
void InsEnd (struct node **start, int x)
{
   if ((*start) == NULL)
   {
      printf ("LINKED LIST IS EMPTY\n");
   }
   else
   {
      struct node *p;
      p = (*start);
      // traverse the linked list to reach the last node
      while ((p->next) != NULL)
      {
         p = p->next;
      }
      // create a new node and insert it after the last node
      struct node *q = getnode();
      q->next = NULL;
      q->data = x;
      p->next = q;
   }
}

// Function to insert a node after a given node
void InsAft (struct node **p, int x)
{
   struct node *q;
   q = getnode(); // get a new node
   q->data = x; // store the data in the node
   q->next = (*p)->next; // make the new node point to the node next to the given node
   (*p)->next = q; // make the given node point to the new node
}

// Function to insert a node in a sorted linked list in ascending order
void InsInOrder (struct node **start, int x)
{
   struct node *p, *q;
   p = (*start);
   q = NULL;
   // traverse the linked list to find the correct position to insert the node
   while (p != NULL && x >= p->data)
   {
      q = p;
      p = p->next;
   }
   // insert the node
   if (q == NULL)
   {
      InsBeg (&(*start), x);
   }
   else
   {
      InsAft (&q, x);
   }
}

// Function to traverse the linked list and print the data of each node
void Traverse (struct node **start)
{
   struct node *p = (*start);
   // traverse the linked list and print the data of each node
   while (p != NULL)
   {
      printf ("%d ", p->data);
      p = p->next;
   }
   printf ("\n");
}


// Function to find the union of two linked lists
void Union(struct node *list1, struct node *list2)
{
struct node *p, *q, *list3;

p = list1;
q = list2;
list3 = NULL;

// Traverse both linked lists and compare the data of each node
while (p != NULL && q != NULL)
{
if ((p->data) < (q->data))
{
InsInOrder (&list3, p->data); // insert the smaller data in the new linked list
p = p->next;
}
else if ((p->data) > (q->data))
{
InsInOrder (&list3, q->data); // insert the smaller data in the new linked list
q = q->next;
}
else
{
InsInOrder (&list3, q->data); // insert the common data in the new linked list
p = p->next;
q = q->next;
}
}

// Traverse the remaining elements of the first linked list, if any
while (p != NULL)
{
InsInOrder (&list3, p->data); // insert the remaining elements in the new linked list
p = p->next;
}

// Traverse the remaining elements of the second linked list, if any
while (q != NULL)
{
InsInOrder (&list3, q->data); // insert the remaining elements in the new linked list
q = q->next;
}

Traverse (&list3); // traverse and print the new linked list
}

// Function to find the intersection of two linked lists
void Intersection(struct node *list1, struct node *list2)
{
struct node *p, *q, *list3;

// initialize pointers p and q to list1 and list2 respectively
p = list1;
q = list2;
// initialize the list3 linked list to NULL
list3 = NULL;

// Traverse both linked lists and compare the data of each node
while (p != NULL && q != NULL)
{
// if data of node p is smaller than data of node q
if ((p->data) < (q->data))
{
// move p to the next node
p = p->next;
}
// if data of node p is greater than data of node q
else if ((p->data) > (q->data))
{
// move q to the next node
q = q->next;
}
// if data of node p is equal to data of node q
else
{
// insert the common data in the new linked list list3
InsInOrder (&list3, q->data);
// move both pointers to their next nodes
p = p->next;
q = q->next;
}
}
// traverse and print the new linked list list3
Traverse (&list3);
}

output: