Union of two linked lists implementation

Union of two linked lists

Given two sorted linked list, find union of two linked lists. Union of two linked lists means collection of all nodes which are present either of the lists only once. For example:

List 1 : 1->2->3->4->5->NULL
List 2 : 2->4->6->7->NULL
Output : 1->2->3->4->5->6->7->NULL
List 1 : 1->2->3->4->NULL
List 2 : 2->4->6->7->9->11->NULL
Output : 1->2->3->4->6->7->9->11->NULL

Methods to find union of two linked lists

Brute force method

Brute force method is to use hash. Scan first list and put all nodes in a hash. Now, scan second list. Check if current node is present in hash, if yes, skip it. If not, add it to hash. At the end, create a linked list from nodes in the hash. This linked list is union of two linked lists given as input. Brute force method works even with non sorted linked lists.

Complexity of brute force method is O(m+n) where m and n are lengths of two lists and additional space complexity of O(m+n) to store on hash.

Search method

Search method requires modification of lists. Scan each node in linked list and find node in second list. If current node is not present in second list, add it to resultant list. Once all nodes of first list are scanned, add second list at end of first linked list. This will given union of two linked list, but not in any particular order.

This method also works for non sorted linked lists, however, complexity is O(m*n).  Two methods discussed till now, will not work if lists contain duplicate nodes.

Using merge sort to find union of two lists

Use merge sort algorithm on linked list with a slight change. In merge sort of linked list, we add node to result list and then advance pointer of one of the list. To find union of two linked lists, add a special case where if nodes are equal, add node to result node and advance both lists to next pointer. Algorithm is very similar to merge sort.

1. Let a and b are two lists whose union is to be found.
2. If a is null, add b to result.
3. If b is null, add a to result
4. If a->data < b->data
   4.a Create new node temp with data as a->data
   4.b Advance a to next pointer and find union of a->next and b.
   4.c set temp->next as result of 4.b
5. If a->data > b->data, repeat 4.a to 4.c with a replaced with b
6. If a->data == b->data
   6.a same as 4.a
   6.b Advance a and b to next and find union of a->next,b->next
   6.c Set temp->next as result of 6.b
7. Return temp

Find union of two list using merge sort implementation

In implementation, there is implicit space complexity of O(m+n), to avoid that iterative implementation is handy.

Iterative method to find union of two linked lists

Complexity of algorithm to find union of two lists is O(m+n).

Here assumption is that two lists are sorted. If list are not sorted, then first sort two lists using merge sort. In that case complexity will be dominated by O(m log m) and O(n log n).

Please share if you find something wrong or something can be improved. Sharing is caring.