700534. Union of Two Linked Lists
Union of Two Linked Lists
Slug: union-of-two-linked-list
Difficulty: Medium
Id: 700534
Topic Tags: Linked List, Hash, Sorting, Data Structures, Algorithms
Company Tags: Flipkart, Amazon, Microsoft, 24*7 Innovation Labs, Komli Media, Taxi4Sure
Summary
The problem is to find the union of two linked lists. The union of two sets is the set that contains all elements from both sets without duplicates. In this case, we are given two sorted linked lists and our task is to create a new sorted linked list that contains all unique elements from both lists.
Detailed Explanation
The approach is to iterate through both lists simultaneously and add each element to a hash set or a balanced binary search tree (BST) if it's not already present. This way, we ensure that every element from both lists is added only once. Finally, we create a new linked list by traversing the hash set or BST in order.
Here's a step-by-step breakdown of the solution:
- Create an empty hash set or a balanced BST.
- Initialize two pointers,
p1andp2, to the beginning of both lists. - While
p1andp2are not null:- If
p1->data <= p2->data, addp1->datato the hash set or BST, incrementp1. - Otherwise, add
p2->datato the hash set or BST, incrementp2.
- If
- Create a new linked list by traversing the hash set or BST in order.
The time complexity of this solution is O(m + n), where m and n are the lengths of the two input lists. The space complexity is also O(m + n) due to the storage required for the new linked list.
Optimized Solutions
Java
public class UnionList {
public static Node unionLists(Node head1, Node head2) {
Set<Integer> set = new HashSet<>();
Node curr = head1;
while (curr != null) {
set.add(curr.data);
curr = curr.next;
}
curr = head2;
while (curr != null) {
if (!set.contains(curr.data)) {
set.add(curr.data);
}
curr = curr.next;
}
Node dummy = new Node(0);
Node prev = dummy;
for (int data : set) {
prev.next = new Node(data);
prev = prev.next;
}
return dummy.next;
}
}