sundeepblue
4/12/2014 - 2:33 PM

## Find the common elements of two linked lists when (a) They are not sorted (b) They are sorted

Find the common elements of two linked lists when (a) They are not sorted (b) They are sorted

``````// two lists are sorted
vector<int> find_common_element_of_two_sorted_lists(ListNode *l1, ListNode *l2) {
vector<int> res;
if(!l1 || !l2) return res;
ListNode *p1 = l1, *p2 = l2;
unordered_set<int> se;
while(p1 && p2) {
if(p1->val == p2->val) {
se.insert(p1->val);
p1 = p1->next;          // forgot!!!
p2 = p2->next;          // forgot!!!
}
else if(p1->val < p2->val)
p1 = p1->next;
else
p2 = p2->next;
}
for(auto i : se) res.push_back(i);
return res;
}

// two lists are unsorted
vector<int> find_common_element_of_two_unsorted_lists(ListNode *l1, ListNode *l2) {
vector<int> res;
if(!l1 || !l2) return res;
unordered_set<int> se;
ListNode *p1 = l1, *p2 = l2;
for(; p1; p1=p1->next)
se.insert(p1->val);
for(; p2; p2=p2->next) {
if(se.find(p2->val) != se.end())
res.push_back(p2->val);
}
return res;
}
``````