主要要考虑有两个链表有交集的情况：
#include <stdio.h>
typedef struct Node
{
struct Node *next;
int value;
}Node, *List;
List merge(List a, List b)
{
Node *p, *pa, *pb, *prea;
if(a == NULL || b == NULL) return;
p = a;
prea = a;
pa = a->next;
pb = b->next;
while(pa && pb)
{
if(pa == pb)
{
pb = NULL;
break;
}
else if(pa->value > pb->value)
//注意两个节点的值相等的时候还不能插进来，防止a节点后的地3个节点与b节点后的第一个节点是同一个节点，
//这时如果a节点后的第1，2个节点与第3个节点（b后的第1个节点）的值相等的话，那么会把b后第1个节点插进来，这样就不能等到a的第3个节点与b的第1个节点比较地址了。
{
prea->next = pb;
pb = pb->next;
prea = prea->next;
prea->next = pa;
}
else
{
if(pa->next == pb->next)
//要判断一下下一个节点是否相等，如果a链表所有节点是0，b链表的第一个节点是0，并且与a链表的节点有交集，如果不判断，这里的最后结果是把b放在a后面，
//这样b的最后有指向a前面那个交集的节点，就会形成一个环了。
{
pb->next = NULL;
}
prea = pa;
pa = pa->next;
}
}
prea->next = pa ? pa : pb;
return p;
}
void print(List a)
{
if(!a) return;
Node *p = a->next;
while(p)
{
printf("%d ", p->value);
p = p->next;
}
putchar('\n');
}
List getList(int a[], int len)
{
int i;
Node *head = (Node*)malloc(sizeof(Node));
Node *p = head;
head->next = NULL;
for(i = 0; i < len; i++)
{
Node *n = (Node*)malloc(sizeof(Node));
n->value = a[i];
p->next = n;
p = n;
}
p->next = NULL;
return head;
}
int main(int argc, char *argv[])
{
{
int a[] = {1, 2, 3, 4};
int b[] = {0, 1, 5};
List la = getList(a, 4);
List lb = getList(b, 3);
print(la);
print(lb);
print(merge(la, lb));
}
printf("---------------\n");
{
int a[] = {0, 0, 0, 0};
int b[] = {0};
List la = getList(a, 4);
List lb = getList(b, 1);
lb->next->next = la->next->next;
print(la);
print(lb);
print(merge(la, lb));
}
{
int a[] = {0, 1, 3, 40};
int b[] = {0};
List la = getList(a, 4);
List lb = getList(b, 1);
lb->next->next = la->next->next->next;
print(la);
print(lb);
print(merge(la, lb));
}
return 0;
}
输出结果：
1 2 3 4
0 1 5
0 1 1 2 3 4 5
---------------
0 0 0 0
0 0 0 0
0 0 0 0 0
0 1 3 40
0 3 40
0 0 1 3 40