CareerCup

/*  merging two linked lists */

node * Merge( node * L1, node * L2 )
{
    if( L1 == NULL )
        return L2;
    else if( L2 == NULL )
        return L1 
    else
    {
        node *p=L1, *q=L2, *r;
        
                while( p->next!= NULL && q!=NULL)
        {
            r = p->next;
            p->next = q;            
			p = q;
			q = r;
        }
        if( p->next == NULL )
        {
            p->next = q;
        }
        return L1;
    }
    
}

This is a recursive implementation of alternateMerge.. the final result is available in the list pointer l1. So the function does not return anything.

The implementation assumes the lists are of equal size, so if any of the list ends, the alternateMerge ends, ignoring the rest of the elements in the other list.

void alternateMerge(node *l1,node *l2)
{
	if(l1==NULL || l2==NULL) return;
	node *temp;
	temp=l1->next;
	l1->next=l2;
	l2=l2->next;
	l1->next->next=temp;
	alternateMerge(temp,l2);
}

//Returns head of merged list.
// lists can be of unequal sizes.

Node alternateMerge(Node a, Node b)
{
    if (a==null) return b;
    if (b==null) return a;
     
    b.next = alternateMerge(a.next, b.next);
    a.next = b;
    return a;
}

Linked List. NA