CareerCup

node* merge(node* n1,node* n2)
{
      node* n;
      if(!n1||!n2)
      {
      	            if(!n1)                     
      	            return n2;
      	            else 
      	            return n1;
      }
      if(n1->val < n2->val)
      {
      
                    n=n1;
                    n->next = merge(n1->next,n2);
      }
      else if(n1->val > n2->val)
      {
      
                    n=n2;
                    n->next = merge(n1,n2->next);
      }
      else
      {
      		    n=n1;
                    n->next=n2;
      		    n->next->next = merge(n1->next,n2->next);
      }
      return n;
}

Please be more specific. What do you mean by Merge ? Are these lists sorted ? Shall we remove duplicate values ?
In general, without any restrictions, we can just att head of second list to tail of first, thats it...

NO HIRE

Candidate cannot even explain a simple interview question properly.

this is merge sort in case of linked lists and you don't have the luxury of using a third list to store the result, you have to modified the given sorted lists in such a way that the combined result is a sorted list with elements from both these lists.

Maintain a pointer to the tail of one linked list. When you need to merge, just use the tail pointer to access the last node of the list and point it's next pointer to the 2nd linked list. Maintaining the tail pointer to the last node of one list is O(1). Merging is also O(1). If maintaining the pointer to the last node of one list is not allowed then the algorithm requires atleast O(n) where 'n' is the length of the smaller of the two linked lists.

Maintain a pointer to the tail of one linked list. When you need to merge, just use the tail pointer to access the last node of the list and point it's next pointer to the 2nd linked list. Maintaining the tail pointer to the last node of one list is O(1). Merging is also O(1). If maintaining the pointer to the last node of one list is not allowed then the algorithm requires atleast O(n) where 'n' is the length of the smaller of the two linked lists.

public void MergeList(SingleLinkedList l1, SingleLinkedList l2)
{
  if(l1.Head == null)
    l1.Head=l2.Head;
  if(l2.Head==null)
    return;
  ListNode index1=l1.Head, index2=l2.Head;
    if(index2.Value < l1.Head.Value)
    {
      l2.Head = l2.Head.Next;
      index2.Next=l1.Head;
      l1.Head = index2;
      index1 = l1.Head;
      index2 = l2.Head;
    }
  while(index1.Next!=null && index2!=null)
  {
    if(index2.Value > index1.Value && index2.Value<=index1.Next.Value)
    {
      temp = index2;
      index2=index2.Next;
      temp.Next = index1.Next;
      index1.Next = temp;
    }
    index1= index1.Next;
  }
  if(index1.Next==null)
    index1.Next = index2;  
}

node * merge (node * l1, node * l2)
{
    node Head={0};
    node *t = &Head;
    while (l1 && l2)
    {
        if (l1->v > l2->v)
        {    t->next = l2; l2 = l2->next; }
        else
        {    t->next = l1; l1 = l1->next; }
        t = t->next;
    }
    if (l1)
        t->next = l1;
    else
        t->next = l2;
    return Head.next;
}

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.

Sorry for late reply and also for the incomplete question: Lists were sorted - merged list should be sorted. Duplicates should not be removed.

Node *  Merge ( Node * H1 , Node *H2 )
{
	if ( ! H1 ) return H2 ;
	if ( ! H2 ) return H1 ;
	if ( H1 -> data < H2 -> data ) 
	{
		H1->next = Merge ( H1 -> next , H2 ) ;
		return H1;
	}
	else
	{
		H2->next = Merge ( H1 , H2 -> next );
		return H2 ;
	}
}

node *merge(node *a, node *b)
{
	node *tmp, *head;
	
	if (a == NULL)
		return b;
	else if (b == NULL)
		return a;

        /* saving the head pointer */		
	if (a->data < b->data)
	{
		tmp = a;
		a = a->next;
	}
	else
	{ 
		tmp = b;
		b = b->next;
	}
	
	head = tmp;
	
        /* looping */
	while(1)
	{
		if (a == NULL)
		{
			tmp->next = b;
			break;
		}
		else if (b== NULL)
		{
			tmp->next = a;
			break;
		}
		else if (a->data < b->data)
		{
			tmp->next = a;
			tmp = tmp->next;
			a = a->next;
		}
		else if (a->data > b->data)
		{
			tmp->next = b;
			tmp = tmp->next;
			b = b->next;
		}
	}
	
	return head;
}