Frequently asked Linked List Interview Question - Union of two linked lists

Problem statement:

Given two linked lists, return the union of two linked lists. This union should include all the distinct elements only. Return the head of the new list.

Example :

Input:

L1 = 9->6->4->2->3->8

L2 = 1->2->8->6->2

Output:

1 2 3 4 6 8 9.

Note: The new list formed should be in non-decreasing order.

Expected Time Complexity: O(N * Log(N))

Expected Auxiliary Space: O(N)

Asked in following companies

24*7 Innovation Labs, Amazon, Flipkart, Komli Media ,Microsoft, Taxi4Sure

Brute force approach:

• Add all the elements of ‘list1’ in union list.
• When traversing the ‘list2’, if that particular element is already present in ‘list1’, then skip that element and if that element is not present in the ‘list1’ then we just need to add that element in the union list.
• Return the head of the resultant union list.

Complexity Analysis:

Time Complexity: O(m*n). Here ‘m’ and ’n’ are number of elements present in the first and second lists respectively

Auxiliary Space: O(1). No use of any data structure for storing values.

Optimal Solution:

A. Using Merge Sort

• Sort the first Linked List using merge sort. This step takes O(mLogm) time.
• Sort the second Linked List using merge sort. This step takes O(nLogn) time.
• Linearly scan both sorted lists to get the union. This step takes O(m + n) time.

Complexity Analysis:

O(mLogm + nLogn) which is better than the brute force approach.

B. Using Hashing

• Since we have to print elements in increasing order, so we need a data structure that can guarantee order.
• Create an empty sorted set.
• Traverse both lists one by one, and add that to the set that we created. This will achieve two things — only unique elements will be added and the since we use sorted set, we will be able to add elements in increasing order naturally.
• Create a dummy Node with value as -1.
• Traverse the set and keep on adding new nodes with respective values from the set.
• Return the new head.

Complexity Analysis:

Time Complexity: O(m+n). Here ‘m’ and ’n’ are number of elements present in the first and second lists respectively

Auxiliary Space: O(m+n). Use of Set data structure.

Code:

public static Node findUnion(Node head1, Node head2) {
    SortedSet < Integer > set1 = new TreeSet < > ();
    Node temp1 = head1;
    while (temp1 != null) {
        set1.add(temp1.data);
        temp1 = temp1.next;
    }
    Node temp2 = head2;
    while (temp2 != null) {
        set1.add(temp2.data);
        temp2 = temp2.next;
    }
    Node dummy = new Node(-1);
    Node prev = dummy;
    for (int i: set1) {
        Node newnode = new Node(i);
        prev.next = newnode;
        prev = prev.next;
    }
    return dummy.next;
}

Thanks for reading.

Happy coding😁