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.

```
/*
```

 * C Program to Find Intersection & Union of 2 Linked Lists

```
 */ 
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int num;
```
```
    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->num != qtemp->num)

```
        {
```
```
            qtemp = qtemp->next;
```
```
        }
```
```
        if (qtemp != NULL)
```
```
        {
```
```
            if (ifront != NULL)
```
```
            {
```

                if (ifront->num == qtemp->num)

```
                {
```

                    ptemp = ptemp->next;

```
                    continue;
```
```
                }
```
```
                ifront = ifront->next;
```
```
            }
```

            itemp = (struct node *)malloc(sizeof(struct node));

```
            itemp->num = qtemp->num;
```
```
            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->num == p->num)
```
```
            {
```
```
                flag = 1;
```
```
            }
```
```
            ufront = ufront->next;
```
```
        }
```
```
        if (flag)
```
```
        {
```
```
            flag = 0;
```
```
        }
```
```
        else
```
```
        {
```

            utemp = (struct node *)malloc(sizeof(struct node));

```
            utemp->num = p->num;
```
```
            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->num == q->num)
```
```
            {
```
```
                flag = 1;
```
```
            }
```
```
            ufront = ufront->next;
```
```
        }
```
```
        if (flag)
```
```
        {
```
```
            flag = 0;
```
```
        }
```
```
        else
```
```
        {
```

            utemp = (struct node *)malloc(sizeof(struct node));

```
            utemp->num = q->num;
```
```
            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->num = 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->num);
```
```
        head = head->next;
```
```
    }
```
```
    printf("\n");
```
```
}
```
```
 
```
```
void release(struct node **head)
```
```
{
```
```
    struct node *temp = *head;
```
```
    while ((*head) != NULL)
```
```
    {
```
```
        (*head) = (*head)->next;
```
```
        free (temp);
```
```
        temp = *head;
```
```
    }
```
```
}
```

$ 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.

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.

« Prev - C Program to Support Arbitrary Precision Arithmetic

» Next - C Program to Implement Doubly Linked List using Singly Linked List

Related Posts:

Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books
Practice Computer Science MCQs
Check Computer Science Books

Recommended Articles: