程序需要考虑如下情况：两个链表（函数参数）都有可能为空，也可能其中一个链表已经遍历完了，另一个链表还有很多元素。
使用递归：
合并操作是非常适合用递归来完成的一类操作，递归实现将会比迭代实现更加清晰且易于理解。尽管如此，你可能也不愿意使用递归来实现这个操作，因为递归方法所使用的栈空间与链表的长度成正比。/*Using Recursion*/
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/*Base cases*/
if(a == NULL)
return (b);
else if(b == NULL)
return (a);
/*Pick either a or b, and recur */
if(a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return (result);
} 原文：http://blog.csdn.net/itjavawfc/article/details/43687701