C Programming Code Examples C > Linked Lists Code Examples Program to Find Intersection & Union of 2 Linked Lists Program to Find Intersection & Union of 2 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 #include <stdio.h> #include <stdlib.h> struct node { int j; struct node *next; }; void create(struct node **); void findunion(struct node *, struct node *, struct node **); void findintersect(struct node *, struct node *, struct node **); void display(struct node *); void release(struct node **); int main() { struct node *phead, *qhead, *intersect, *unionlist; phead = qhead = intersect = unionlist = NULL; printf("Enter elements in the list 1\n"); create(&phead); printf("\nEnter elements in the list 2\n"); create(&qhead); findunion(phead, qhead, &unionlist); findintersect(phead, qhead, &intersect); printf("\nDisplaying list 1:\n"); display(phead); printf("Displaying list 2:\n"); display(qhead); printf("Displaying the union of the 2 lists:\n"); display(unionlist); printf("Displaying the intersection of the 2 lists:\n"); if (intersect == NULL) { printf("Null\n"); } else { display(intersect); } release(&phead); release(&qhead); release(&unionlist); release(&intersect); return 0; } void findintersect(struct node *p, struct node *q, struct node **intersect) { struct node *ptemp, *qtemp, *itemp, *irear, *ifront; ptemp = p; while (ptemp != NULL) { qtemp = q; ifront = *intersect; while (qtemp != NULL && ptemp->j != qtemp->j) { qtemp = qtemp->next; } if (qtemp != NULL) { if (ifront != NULL) { if (ifront->j == qtemp->j) { ptemp = ptemp->next; continue; } ifront = ifront->next; } itemp = (struct node *)malloc(sizeof(struct node)); itemp->j = qtemp->j; itemp->next = NULL; if (*intersect == NULL) { *intersect = itemp; } else { irear->next = itemp; } irear = itemp; } ptemp = ptemp->next; } } void findunion(struct node *p, struct node *q, struct node **unionlist) { struct node *utemp, *ufront, *urear; int flag = 0; while (p != NULL) { ufront = *unionlist; while (ufront != NULL) { if (ufront->j == p->j) { flag = 1; } ufront = ufront->next; } if (flag) { flag = 0; } else { utemp = (struct node *)malloc(sizeof(struct node)); utemp->j = p->j; utemp->next = NULL; if (*unionlist == NULL) { *unionlist = utemp; } else { urear->next = utemp; } urear = utemp; } p = p->next; } while (q != NULL) { ufront = *unionlist; while (ufront != NULL) { if (ufront->j == q->j) { flag = 1; } ufront = ufront->next; } if (flag) { flag = 0; } else { utemp = (struct node *)malloc(sizeof(struct node)); utemp->j = q->j; utemp->next = NULL; if (*unionlist == NULL) { *unionlist = utemp; } else { urear->next = utemp; } urear = utemp; } q = q->next; } } void create(struct node **head) { struct node *temp, *rear; int ch, a; do { printf("Enter a number: "); scanf("%d", &a); temp = (struct node *)malloc(sizeof(struct node)); temp->j = a; temp->next = NULL; if (*head == NULL) { *head = temp; } else { rear->next = temp; } rear = temp; printf("Do you want to continue [1/0] ? "); scanf("%d", &ch); } while (ch != 0); } void display(struct node *head) { while (head != NULL) { printf("%d ", head->j); head = head->next; } printf("\n"); } void release(struct node **head) { struct node *temp = *head; while ((*head) != NULL) { (*head) = (*head)->next; free (temp); temp = *head; } }
