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;
  p->next = (*head);
  (*head) = p;
}

/* 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()
{
  /* Start with two empty lists */
  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;
}

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

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.