C Program to Find Intersection and Union of Two Linked Lists

This C Program finds the intersection and union of 2 linked lists. Intersection is a set of elements that are common in both lists while union is a set of all unique elements in both the lists

Here is a source code of the C program finds the intersection and union of 2 linked lists. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Find Intersection & Union of 2 Linked Lists 
  3.  */ 
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. struct node
  8. {
  9.     int num;
  10.     struct node *next;
  11. };
  12.  
  13. void create(struct node **);
  14. void findunion(struct node *, struct node *, struct node **);
  15. void findintersect(struct node *, struct node *, struct node **);
  16. void display(struct node *);
  17. void release(struct node **);
  18.  
  19. int main()
  20. {
  21.     struct node *phead, *qhead, *intersect, *unionlist;
  22.  
  23.     phead = qhead = intersect = unionlist = NULL;
  24.     printf("Enter elements in the list 1\n");
  25.     create(&phead);
  26.     printf("\nEnter elements in the list 2\n");
  27.     create(&qhead);
  28.     findunion(phead, qhead, &unionlist);
  29.     findintersect(phead, qhead, &intersect);
  30.     printf("\nDisplaying list 1:\n");
  31.     display(phead);
  32.     printf("Displaying list 2:\n");
  33.     display(qhead);
  34.     printf("Displaying the union of the 2 lists:\n");
  35.     display(unionlist);
  36.     printf("Displaying the intersection of the 2 lists:\n");
  37.     if (intersect == NULL)
  38.     {
  39.         printf("Null\n");
  40.     }
  41.     else
  42.     {
  43.         display(intersect);
  44.     }
  45.     release(&phead);
  46.     release(&qhead);
  47.     release(&unionlist);
  48.     release(&intersect);
  49.  
  50.     return 0;
  51. }
  52.  
  53. void findintersect(struct node *p, struct node *q, struct node **intersect)
  54. {
  55.     struct node *ptemp, *qtemp, *itemp, *irear, *ifront;
  56.  
  57.     ptemp = p;
  58.     while (ptemp != NULL)
  59.     {
  60.         qtemp = q;
  61.         ifront = *intersect;
  62.         while (qtemp != NULL && ptemp->num != qtemp->num)
  63.         {
  64.             qtemp = qtemp->next;
  65.         }
  66.         if (qtemp != NULL)
  67.         {
  68.             if (ifront != NULL)
  69.             {
  70.                 if (ifront->num == qtemp->num)
  71.                 {
  72.                     ptemp = ptemp->next;
  73.                     continue;
  74.                 }
  75.                 ifront = ifront->next;
  76.             }
  77.             itemp = (struct node *)malloc(sizeof(struct node));
  78.             itemp->num = qtemp->num;
  79.             itemp->next = NULL;
  80.             if (*intersect == NULL)
  81.             {
  82.                 *intersect = itemp;
  83.             }
  84.             else
  85.             {
  86.                 irear->next = itemp;
  87.             }
  88.             irear = itemp;
  89.         }
  90.         ptemp = ptemp->next;
  91.     }
  92. }
  93.  
  94. void findunion(struct node *p, struct node *q, struct node **unionlist)
  95. {
  96.     struct node *utemp, *ufront, *urear;
  97.     int flag = 0;
  98.  
  99.     while (p != NULL)
  100.     {
  101.         ufront = *unionlist;
  102.         while (ufront != NULL)
  103.         {
  104.             if (ufront->num == p->num)
  105.             {
  106.                 flag = 1;
  107.             }
  108.             ufront = ufront->next;
  109.         }
  110.         if (flag)
  111.         {
  112.             flag = 0;
  113.         }
  114.         else
  115.         {
  116.             utemp = (struct node *)malloc(sizeof(struct node));
  117.             utemp->num = p->num;
  118.             utemp->next = NULL;
  119.             if (*unionlist == NULL)
  120.             {
  121.                 *unionlist = utemp;
  122.             }
  123.             else
  124.             {
  125.                 urear->next = utemp;
  126.             }
  127.             urear = utemp;
  128.         }
  129.         p = p->next;
  130.     }
  131.     while (q != NULL)
  132.     {
  133.         ufront = *unionlist;
  134.         while (ufront != NULL)
  135.         {
  136.             if (ufront->num == q->num)
  137.             {
  138.                 flag = 1;
  139.             }
  140.             ufront = ufront->next;
  141.         }
  142.         if (flag)
  143.         {
  144.             flag = 0;
  145.         }
  146.         else
  147.         {
  148.             utemp = (struct node *)malloc(sizeof(struct node));
  149.             utemp->num = q->num;
  150.             utemp->next = NULL;
  151.             if (*unionlist == NULL)
  152.             {
  153.                 *unionlist = utemp;
  154.             }
  155.             else
  156.             {
  157.                 urear->next = utemp;
  158.             }
  159.             urear = utemp;
  160.         }
  161.         q = q->next;
  162.     }
  163. }
  164.  
  165. void create(struct node **head)
  166. {
  167.     struct node *temp, *rear;
  168.     int ch, a;
  169.  
  170.     do
  171.     {
  172.         printf("Enter a number: ");
  173.         scanf("%d", &a);
  174.         temp = (struct node *)malloc(sizeof(struct node));
  175.         temp->num = a;
  176.         temp->next = NULL;
  177.         if (*head == NULL)
  178.         {
  179.             *head = temp;
  180.         }
  181.         else
  182.         {
  183.             rear->next = temp;
  184.         }
  185.         rear = temp;
  186.         printf("Do you want to continue [1/0] ? ");
  187.         scanf("%d", &ch);
  188.     } while (ch != 0);
  189. }
  190.  
  191. void display(struct node *head)
  192. {
  193.     while (head != NULL)
  194.     {
  195.         printf("%d   ", head->num);
  196.         head = head->next;
  197.     }
  198.     printf("\n");
  199. }
  200.  
  201. void release(struct node **head)
  202. {
  203.     struct node *temp = *head;
  204.     while ((*head) != NULL)
  205.     {
  206.         (*head) = (*head)->next;
  207.         free (temp);
  208.         temp = *head;
  209.     }
  210. }

$ gcc unionandintersect.c 
$ ./a.out
Enter elements in the list 1
Enter a number: 1
Do you want to continue [1/0] ? 1
Enter a number: 2
Do you want to continue [1/0] ? 1
Enter a number: 5
Do you want to continue [1/0] ? 1
Enter a number: 6
Do you want to continue [1/0] ? 1
Enter a number: 8
Do you want to continue [1/0] ? 1
Enter a number: 9
Do you want to continue [1/0] ? 0
 
Enter elements in the list 2
Enter a number: 1
Do you want to continue [1/0] ? 1
Enter a number: 3
Do you want to continue [1/0] ? 1
Enter a number: 5
Do you want to continue [1/0] ? 1
Enter a number: 7
Do you want to continue [1/0] ? 1
Enter a number: 9
Do you want to continue [1/0] ? 0
 
Displaying list 1:
1   2   5   6   8   9   
Displaying list 2:
1   3   5   7   9   
Displaying the union of the 2 lists:
1   2   5   6   8   9   3   7   
Displaying the intersection of the 2 lists:
1   5   9

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.