C 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

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>

7. struct node

8. {

9.     int num;

10.     struct node *next;

11. };

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 **);

19. int main()

20. {

21.     struct node *phead, *qhead, *intersect, *unionlist;

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);

50.     return 0;

51. }

53. void findintersect(struct node *p, struct node *q, struct node **intersect)

54. {

55.     struct node *ptemp, *qtemp, *itemp, *irear, *ifront;

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

94. void findunion(struct node *p, struct node *q, struct node **unionlist)

95. {

96.     struct node *utemp, *ufront, *urear;

97.     int flag = 0;

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

165. void create(struct node **head)

166. {

167.     struct node *temp, *rear;

168.     int ch, a;

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

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

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