问题描述：已知有两个递增的正整数序列A和B，序列中元素个数未知，同一序列中不会有重复元素出现，有可能某个序列为空。你的任务是求这两个序列的差集A-B与交集A+B。A-B就是仅由在A中出现而不在B中出现的元素所构成的集合，设为C1；A+B就是既在A中出现也在B中出现的元素所构成的集合，设为C2。
要求：
建立四个单链表，分别为A、B、C1、C2，并使用A、B这两个链表存储两个正整数序列，然后将集合A-B中的元素存储在链表C1中，将集合A+B中的元素存储在链表C2中。正整数序列的输入是按照递增顺序输入的,用-1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计-1）。在程序结束前要释放链表A、B、C1、C2中的所有节点。
输入与输出要求：依次输入两个递增的正整数序列A和B，序列元素的个数未知，但以输入“-1”结束，每个正整数序列占一行。输出链表C1中的元素，占一行；然后是链表C2中的元素，占一行。每行的每个元素后有一个空格，注意最后一个元素后只有换行符，如果某个链表为空则，则输出“There is no item in XX list.”。
程序运行效果：
Sample 1:
Please input the elements of list A:1 2 3 4 5 6 7 -1
Please input the elements of list B:2 3 6 -1
输出
The list C1:1 4 5 7
The list C2:2 3 6
Sample 2:
Please input the elements of list A:-1
Please input the elements of list B:-1
输出
There is no item in C1 list.
There is no item in C2 list.
又是单链表，把一个节点插入到另一个链表里都要重新申请过空间。因为作业要求注释，所以我写注释写得好~详细啊。
/*
天啦噜，今天去欢乐谷玩得好嗨啊，虽然当了好久的大功率电灯泡，不过后来玩得好棒~
晚上回来做上机题时，总觉得自己在过山车上失重着，这感觉好持久啊 →_→
*/
#include<stdio.h>
typedef struct List
{
int v;
struct List *next;
} list;
list *A,*B,*C1,*C2,*p,*HeadA,*HeadB,*HeadC1,*HeadC2,*p1,*p2,*tmp,*tp,*mp;
int main()
{
int a;
//读list A
printf("Please input the element of list A:");
while(~scanf("%d",&a)&&a!=-1)
{
//先申请空间
p=malloc(sizeof(list));
if(p!=NULL)
{
//申请成功则把节点p插入到A
p->v=a;
if(A!=NULL)
A->next=p;
else
HeadA=p;
A=p;
}
}
if(A!=NULL)//A可能为空
A->next=NULL;
//读list B
printf("Please input the element of list B:");
while(~scanf("%d",&a)&&a!=-1)
{
p=malloc(sizeof(list));
if(p!=NULL)
{
p->v=a;
if(B!=NULL)
B->next=p;
else
HeadB=p;
B=p;
}
}
if(B!=NULL)B->next=NULL;
//开始构建C1
p1=HeadA;
p2=HeadB;
while(p1!=NULL&&p2!=NULL)
{
//listA的当前元素比listB的小
if(p1->v<p2->v)
{
//新建节点tp,tp->v为p1的v
tp=malloc(sizeof(list));
tp->v=p1->v;
//tp插入到C1中
if(C1!=NULL)
C1->next=tp;
else
HeadC1=tp;
C1=tp;
//list A考虑下一个元素
p1=p1->next;
}
else if(p1->v==p2->v)
{
//两个list都考虑下一个元素
p1=p1->next;
p2=p2->next;
}
else if(p1->v>p2->v)
//listB考虑下一个元素
p2=p2->next;
}
//把list A剩余的元素（不可能与list B冲突了）都插入C1
while(p1!=NULL)
{
tp=malloc(sizeof(list));
tp->v=p1->v;
if(C1!=NULL)
C1->next=tp;
else
HeadC1=tp;
C1=tp;
p1=p1->next;
}
if(C1!=NULL)C1->next=NULL;
//开始构建C2
p1=HeadA;
p2=HeadB;
while(p1!=NULL&&p2!=NULL)
{
if(p1->v<p2->v)
p1=p1->next;
else if(p1->v==p2->v)
{
tp=malloc(sizeof(list));
tp->v=p1->v;
if(C2!=NULL)
C2->next=tp;
else
HeadC2=tp;
C2=tp;
p1=p1->next;
p2=p2->next;
}
else if(p1->v>p2->v)
p2=p2->next;
}
if(C2!=NULL)C2->next=NULL;
//开始输出，一边释放C1、C2的内存
if(HeadC1==NULL)printf("There is no item in C1 list.");
else
{
printf("The list C1:");
while(HeadC1!=NULL)
{
tmp=HeadC1;
printf("%d ",tmp->v);
HeadC1=HeadC1->next;
free(tmp);
}
}
if(HeadC2==NULL)printf("\nThere is no item in C2 list.");
else
{
printf("\nThe list C2:");
while(HeadC2!=NULL)
{
tmp=HeadC2;
printf("%d ",tmp->v);
HeadC2=HeadC2->next;
free(tmp);
}
}
//释放listA和listB的内存
while(HeadA!=NULL)
{
tmp=HeadA;
HeadA=HeadA->next;
free(tmp);
}
while(HeadB!=NULL)
{
tmp=HeadB;
HeadB=HeadB->next;
free(tmp);
}
return 0;
}
原文：http://www.cnblogs.com/flipped/p/5296996.html