CareerCup

Since no information about not using additional storage is given. I assume we can use HashSet to do the job of intersection.
Algorithm
1. Traverse list 1 and insert into hashset
2. Traverse list 2 and insert into hashset
3. Create the new list by traversing each element in hashset and creating links appropriately
4. Return his newly created list

public LinkedList<Node> LinkedListsUnion(Node root1, Node root2)
{
  HashSet<int> elems= new HashSet<int>();
  while(root1.Next != null)
  {
   elems.Insert(root1.Data);
   root1=root1.Next;
  } 
  while(root2.Next!=null)
  {
   elems.Insert(root2.Data);
   root2=root2.Next;
  }
  LinkeList ll= new LinkedList();
  foreach(int item in elems)
  {
    Node n= new Node(item);
    if(ll.Root==null)
    {
      ll.Root=n;
    } 
    else
    {
      Node temp=ll.root;
      //Traverse till the end of the list
      //to insert at last
      // but since ordering is not important we can even 
      // change the head ptr to the new node  
      while(temp.Next==null)
        temp=temp.Next;
      temp.Next=n;
    }      
    return ll;
  }

I have one doubt? Whether we have to create another link list or we have to use the existing nodes?
I am assuming that we have to reuse the existing nodes. Now in this case we have to delete the duplicate nodes also.

my soln:
Start from first link list,insert data in hash table. If any duplicate element found then delete that node from link list. Now when reach at the end of first link list , point the list next pointer to second list. do the same for second list also.

node_type *union_of_two_unsorted_link_list(node_type *head1 , node_type *head2)
{
node_type *temp;
node_type *node_to_be_deleted;
node_type *head;
int ret_val=SUCCESS;

if(head1)
{
head=head1;
temp=head1;
}
else
{
head=head2;
temp=head2;
}

if(temp)
{
insert_key_in_hash_table(temp->data);
while(temp->next)
{
ret_val=insert_key_in_hash_table(temp->next->data);
if(ret_val==DUPLICATE)
{
node_to_be_deleted=temp->next;
temp->next=node_to_be_deleted->next;
free(node_to_be_deleted);
}
else
{
temp=temp->next;
}
}

if(head !=head2)
{
temp->next=head2;
while(temp->next)
{
ret_val=insert_key_in_hash_table(temp->next->data);
if(ret_val==DUPLICATE)
{
node_to_be_deleted=temp->next;
temp->next=node_to_be_deleted->next;
free(node_to_be_deleted);
}
else
{
temp=temp->next;
}
}
}
}
return head;
}


For complete program or code see "goursaha.freeoda.com/DataStructure/Unionof2UnsortedLinkList.html"

MS IDC makes fool of people.
People have to come to office on weekends due to workload and do night outs, no work life balance. They pay 10-20% more make people labour.

Do take the feedback from employees before joining MS.

And work is junk, all junk wor from Redmond is transferred to IDC. Ask any team, whether they design, implement products or just do porting or maintenance or make tools.

node* linkedListUnion(node *first, node *second)
{
Hashtable<int> h1;
node *result=NULL;
while(!first)
{
if !(h1.contains(first->data))
{
result.Add(first);
h1.Add(first->data);
}
}
while(!second)
{
if !(h1.contains(second->data))
{
result.Add(second);
h1.Add(second->data);
}
}
return result;
}

Forgot to increment first and second pointer in the previous post.

node* linkedListUnion(node *first, node *second)
{
   Hashtable<int> h1;
   node *result=NULL;
   while(!first)
   {
     if !(h1.contains(first->data))
     {
        result.Add(first);
        h1.Add(first->data);
     } 
     first=first->next;
   } 
   while(!second)
   {
     if !(h1.contains(second->data))
     {
        result.Add(second);
        h1.Add(second->data);
     }
     second=second->next;
   }
   return result;
}

Since they original lists have many duplicates why not point the end of one list to the beginning of the other?

Creating a hash table would extra space, and the size of table would be unknown too. How about an O(nlog(n)) solution?

1. Sort the two linked lists in O(nlog(n)). [This is slightly difficult, but is feasible].
2. Merge the two lists into one linked list in O(n). This won't require any extra space, just old links to be removed and new ones to be created.
3. Remove duplicates from the single linked list in O(n).