{"id":3819,"date":"2021-08-12T06:44:39","date_gmt":"2021-08-12T06:44:39","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3819"},"modified":"2022-11-04T10:23:58","modified_gmt":"2022-11-04T10:23:58","slug":"union-and-intersection-of-two-linked-lists","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/union-and-intersection-of-two-linked-lists\/","title":{"rendered":"Union and Intersection of two Linked Lists"},"content":{"rendered":"

\"\"<\/p>\n

Introduction<\/h3>\n

In the below article, we are going to see how Union is going to work with the linked lists. Generally, if we talk about the union of two linked lists, then there will be a union list which will contain all the elements from both of the lists but common elements will appear once in the union list. Let’s get into the approach of union of two linked lists and intersection of two linked lists <\/p>\n<\/p>\n

Problem Statement of union of two linked lists and how to find the intersection of two linked lists.<\/h3>\n

In this question, we are given two singly-linked lists. We have to find the Union and Intersection of the given lists.<\/p>\n

Problem Statement Understanding for union and intersection of two linked lists
\n<\/h3>\n

Union<\/strong> – All the elements that are in at least one of the two lists.<\/p>\n

Intersection<\/strong> – Only the elements which are present in both lists.<\/p>\n

Suppose the lists are:<\/strong><\/p>\n

L1 : 1 – > 2 – > 3<\/p>\n

L2 : 2- > 3 – > 4<\/p>\n

So, the union (elements that are in atleast one of the two lists) will be:<\/p>\n

Union List:<\/strong> 1 – > 2 – > 3 – > 4<\/p>\n

The intersection (elements that are present in both the lists) will be:<\/p>\n

Intersection List:<\/strong> 2 – > 3<\/p>\n

Input<\/strong><\/p>\n

L1 : <\/p>\n

\"\"<\/p>\n

L2 :<\/p>\n

\"\"<\/p>\n

Output<\/strong><\/p>\n

Intersection List: 2 – > 3<\/p>\n

Union List: 1 – > 2 – > 3 – > 4<\/p>\n

Explanation:<\/strong> As the common elements of L1 and L2 are 2 and 3, they appear in the Intersection list. For the Union List, all the elements of L1 and L2 are considered, but no repetitions. So that’s why 2 and 3 are only present once in the union list.<\/p>\n

While creating the lists, we do not have to worry about the order of the elements. They can be in any order.<\/p>\n

This question is a pretty easy one. The first approach that comes to mind is to pick one element from one list, then traverse through the other list, and keep adding to output lists if necessary. But, can we do better? Yes. We can use hashing. Let us have a glance at the approaches<\/p>\n

Approach (Nested List Traversal)for union of two linked lists<\/h3>\n

The approach is going to be pretty simple. <\/p>\n

Intersection List<\/strong> – Create an empty result list. Traverse through the first list, and look for every element in the second list. If the element is present in the second list, then add that element to the result list.<\/p>\n

Union List<\/strong> – Create an empty result list. Traverse through the first list and add all of its elements to the result list. Now, traverse through the second list. If an element of the second list is already present in the result list, then do not insert it into the result list, otherwise insert it.<\/p>\n

Time Complexity of union of two linked lists<\/strong> – O(m*n), where m and n are the sizes of the two input lists.<\/p>\n

Space Complexity union of two linked lists<\/strong> – O(1), as only temporary nodes are being created for list traversal.<\/p>\n

There is another approach that uses hashing. The time complexity of that approach is better than the time complexity of this approach, so let us have a look at that approach as well.<\/p>\n

Approach (Hashing)for union and intersection of two linked lists
\n <\/h3>\n

This approach is going to use hashing. A very simple application of hashing.<\/p>\n

Union List<\/strong> – Create an empty result list and an empty hash table. Traverse both the linked lists one by one. Insert every element in the hash table. Now, we will traverse through the hash table and insert all the elements in the new list. As a hash table only stores unique keys, we will automatically get the union list.<\/p>\n

Intersection List<\/strong> – Create an empty result list and an empty hash table. Traverse through both the list, and increment the frequency of every element. Now, we will traverse through the hash table, and only the elements whose frequency is 2 will be inserted in the result list. As frequency 2 ensures that the element is present in both lists.<\/p>\n

Algorithm for union and intersection of two linked lists
\n<\/h3>\n

Union List<\/strong><\/p>\n

    \n
  • Create an empty list and an empty map.<\/li>\n
  • Insert all the elements of both the lists in the map as key and their frequencies as values.<\/li>\n
  • Traverse through the map and keep pushing all the elements of the map in the result list.<\/li>\n
  • As a map only stores unique values, we will automatically get the union.<\/li>\n
  • Return the result list.<\/li>\n<\/ul>\n

    Intersection List<\/strong><\/p>\n

      \n
    • Create an empty list and an empty map.<\/li>\n
    • Insert all the elements of both the lists in the map as key, and their frequencies as values<\/li>\n
    • Traverse through the map and add all those elements in the result list, whose frequency is two.<\/li>\n
    • As the frequency is two, this means that the element is present in both lists. Here, we are assuming that there are no repetitions in the given lists.<\/li>\n
    • Return the result list.<\/li>\n<\/ul>\n

      Dry Run for union and intersection of two linked lists
      \n <\/h3>\n

      Union List<\/strong><\/p>\n

      \"\"<\/p>\n

      Intersection List<\/strong><\/p>\n

      \"\"<\/p>\n

      Code Implementation for union and intersection of two linked lists
      \n<\/h3>\n\t\t\t\t\t\t