Part 3: LinkedList Related Algorithm Interview Questions(Union and Intersection)

Also Check: Algorithms and System Design Interview Questions

Create a Union and Intersection of two Linked Lists.
Solution 1: Using Merge Sort.
In this approach you need to sort both the lists,this will take O(mLogm) and O(nLogn) time.
Now we will iterate both the sorted lists to get the union and intersection, it will take O(m + n) time
Time complexity of this method is O(mLogm + nLogn).

Solution 2:Use Hashing
We can use HashTable to find the Union and Intersection of two Linked Lists. Here we are assuming that there are no duplicates in each list. Time Complexity would be O(m+n).

For Union:
1). Create the result list, initialize it with NULL and create an empty hash table.
2). Start traversing the givens lists one by one. During iteration, look the element in the hash table. If the element is not present, then insert the element to the result list and in the hash table as well. Else if the element is present, then ignore it.

For Intersection:
1). Create the result list, initialize it with NULL and create an empty hash table.
2). Start traversing the first list, and insert each element in the hash table.
3). Now traverse the second list. During iteration, look the element in the hash table. If the element is not present, then insert the element to the result list and in the hash table as well. Else if the element is present, then ignore it.

Write a function to get the intersection point of two Linked Lists.
Solution 1: Nested Loop
1). We will use 2 nested loops. In the outer loop will be for each node of the 1st list and inner loop will be for 2nd list.
2). In the inner loop, we will check if any of nodes of the 2nd list is same as the current node of the first linked list.

The time complexity of this approach will be O(M * N), where m and n are the numbers of nodes in two lists.

Solution 2: Node count difference.
1). We will get the count of the nodes in the both the lists, lets say c1 and c2 are the number of nodes on 1st and 2nd list.
2). Now we will get the difference of node counts, d = abs(c1 – c2).
3). We will start traversing the bigger list from the first node till dth node. From here onwards both the lists have equal no of nodes.
4). Now we can traverse both the lists in parallel till we come across a common node.



-K Himaanshu Shuklaa..