Intersection among elements of Linked List

Question

Given two unsorted singly-linked lists each with n distinct elements. There exists an efficient intersection algorithm, that computes and returns a new list with common elements between the input lists. How much time does the intersection algorithm requires in worst case, if it is allowed to use constant extra space only?

Comments

@Magma

I like ur procedure. Where is fault in it?

@Mk Utkarsh

I cannot understand how r u applying merge sort

Can u derive it more

And where is fault in @Magma's procedure?

---

For @magma it takes O(n) space

 

In java we have Hashmap which does similar function, but we need space to construct hashtable over there as well

---

@ kumar.dilip

Your algo finds the physical intersection of the two linked lists i.e. it finds whether two lists share some nodes with same address (and hence value).

Here we are asked to find the common values only and not the physical intersection.

Let LLs be represented like <value,address>. So if LL1 is <1,100>,<4,200> and LL2 is <4,300>, <3,400> then their intersection would be 4 even if there is no common node.