Code:

typedef struct listnode {
char data;
struct listnode *next;
} ListNode;

Code:

ListNode *merge(ListNode *a, ListNode *b)
{
ListNode *head = NULL, **curr = &head;
while (a && b) {
if (a->data <= b->data) {
*curr = a;
a = a->next;
} else {
*curr = b;
b = b->next;
}
curr = &(*curr)->next;
}
if (a) *curr = a;
if (b) *curr = b;
return head;
}

Or recursively (but "inefficient" since it's not tail recursion) :

Code:

ListNode *merge2(ListNode *a, ListNode *b )
{
if (a && (!b || a->data <= b->data))
{
a->next = merge2(a->next, b);
return a;
}
else if (b)
{
b->next = merge2(a, b->next);
return b;
}
return NULL;
}