Last Updated: Mar 27, 2024
Difficulty: Medium

# Union and Intersection of Two Linked Lists (Hashing)

## Introduction

This blog covers a linked list problem. Linked lists are one of the most essential and often asked data structures in programming contests and technical interviews. There are various standard linked list problems and techniques. This blog tackles a coding task that involves finding the union and intersection of two Linked Lists using the hashing approach.

Recommended Topic, Floyds Algorithm

### Problem Statement

We have to generate union and intersection lists that should include the union and intersection of the elements in the given linked lists. The order of the elements in the union and intersection of two linked lists is not relevant.

### Sample Examples

Input

List1:

List2:

Output

Intersection:

Union:

Explanation

These two lists have 14 and 25 nodes in common. The union lists include all of the nodes from both lists.

Input

List1:

List2:

Output

Intersection:

Union:

Explanation

These two lists have 10 and 24 nodes in common. The union lists include all of the nodes from both lists.

## Approach

The approach is quite straightforward. It includes traversing both the linked lists and storing the current element with the number of occurrences in a map. For getting the union list, we store all the elements of the map in the resultant list and for the intersection list, only store the elements with occurrence equal to 2 in the resultant intersection list.

### Algorithm

1. First, begin traversing both lists. Store the current element of both lists with its occurrence in the map.

2. To generate a Union list, store all of the map's elements in the resulting list.

3. To make an Intersection list, store only entries with an occurrence of 2 since 2 indicates that they are present in both lists.

### Implementation

``````// C++ program to find union and intersection lists of
// two linked lists in O(m+n) time using hashing approach.
#include <bits/stdc++.h>
using namespace std;

/*List node */
struct Node
{
int val;
struct Node *next;
};

/* Function for inserting a node at the
beginning of a list*/
void begin_push(struct Node **head, int new_val)
{
struct Node *p = (struct Node *)malloc(sizeof(struct Node));
p->val = new_val;
}

/* Function to store the
elements of both the given list */
void storeElement(struct Node *h1, struct Node *h2,
unordered_map<int, int> &m)
{
struct Node *p1 = h1;
struct Node *p2 = h2;

// Traverse both the lists
while (p1 != NULL || p2 != NULL)
{
// store element in the map
if (p1 != NULL)
{
m[p1->val]++;
p1 = p1->next;
}

if (p2 != NULL)
{
m[p2->val]++;
p2 = p2->next;
}
}
}

/* Function to get the union of two
linked lists h1 and h2 */
struct Node *Union(
unordered_map<int, int> m)
{
struct Node *r = NULL;

// Push all the elements from the map in
// the union list
for (auto it = m.begin(); it != m.end(); it++)
begin_push(&r, it->first);

return r;
}

/* Function to get the intersection of
two linked lists h1 and h2 */
struct Node *Intersection(
unordered_map<int, int> m)
{
struct Node *r = NULL;

/* Push only the nodes with elements
having occurrence of 2 as it
implies that the element is
present in both the lists */
for (auto it = m.begin();
it != m.end(); it++)
if (it->second == 2)
begin_push(&r, it->first);

return r;
}

/* Function to print all the nodes of the list*/
void listPrint(struct Node *root)
{
while (root != NULL)
{
if (root->next == NULL)
break;

// Print the value of the node.
cout << root->val << " -> ";
root = root->next;
}
if (root != NULL)
{
cout << root->val << endl;
}
}

/* Prints union and intersection of
two linked lists with h1 and h2. */
void printUnionIntersection(Node *h1,
Node *h2)
{
/* Store every element of
both lists in the map */
unordered_map<int, int> m;
storeElement(h1, h2, m);
Node *intersectionList = Intersection(m);
Node *unionList = Union(m);
printf("\nIntersection list: \n");
listPrint(intersectionList);
printf("\nUnion list: \n");
listPrint(unionList);
}

/* Driver program*/
int main()
{
struct Node *h1 = NULL;
struct Node *h2 = NULL;

/* create a linked list 25 -> 15 -> 14 -> 20 */
begin_push(&h1, 20);
begin_push(&h1, 14);
begin_push(&h1, 15);
begin_push(&h1, 25);

/* create a linked list 8 -> 14 -> 2 -> 25 */
begin_push(&h2, 25);
begin_push(&h2, 2);
begin_push(&h2, 14);
begin_push(&h2, 8);
printf("First list: \n");
listPrint(h1);
printf("\nSecond list: \n");
listPrint(h2);
printUnionIntersection(h1, h2);
return 0;
}``````

Output

``````First list:
25->15->14->20
Second list:
8->14->2->25
Intersection list:
25->14
Union list:
25->8->15->2->14->20``````

#### Time Complexity

The time complexity of the above approach is O(m+n), where m and n are the number of nodes in the two linked lists.

We have to traverse both the lists, store the elements in Hash-map and update the respective count.

#### Space Complexity

The space complexity of the above approach is O(m+n).

It's due to using the Hash-map data structure for storing values.

### What is Hashing?

Hashing is a technique or procedure that uses a hash function to map keys and values into a hash table.

### What is a hash table?

A hash table is a data structure that stores data associatively. Data is kept in an array format in a hash table, with each data item having its own unique index value..

### What are the common implementations of the Linked list?

Linked lists are useful because they allow for quick insertion and deletion. Stacks, queues, and other abstract data types can be implemented using them.

### What is a circular Linked list?

There are no endings to circular linked lists. Each node in a circular linked list has a successor, and the final node instead of NULL refers to the first node.

## Conclusion

This article extensively discussed the problem of finding the Union and Intersection of two Linked Lists using hashing and its time and space complexities.

We hope this blog has helped you enhance your knowledge regarding Linked Lists. After reading about the Linked Lists, are you not feeling excited to read/explore more articles on this topic? Don't worry, Coding Ninjas has you covered. To learn, see article on linked lists here.

Also Read - Selection Sort in C

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Topics covered
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.