算法：
typedef struct Node {
ElemType data;
struct Node * next; }Node,*LinkList;
void Difference(LinkList LA,LinkList LB) {
Node *p,*q,*pre,*r; pre=LA; p=LA->next; while(p!=NULL) { q=LB->next; while(p->data!=q->data&&q!=NULL) /*查找有无相同元素*/ q=q->next; if(p->data==q->data) /*有相同元素*/ { r=p; pre->next=p->next;/*本来pre->next=p,现改为pre->next=p->next*/ p=p->next; /*下一次判断p->next*/ free(r); /*释放被删除的元素的空间*/ } else { pre=p; /*也可写为pre=pre->next*/ p=p->next; } } }
3、有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将他们合并成一个单链表LC，要求LC也是非递减有序排列。
要求：新表LC利用现有的表LA和LB中的元素结点空间，而不要额外申请结点空间。例如LA?(2,2,3),LB?(1,3,3,4)，则
LC?(1,2,2,3。,3
算法思想：要求利用现有的表LA和LB中的结点空间来建立新表LC，可通过更改结点的next域来重建新的元素之间的线性关系。
为包证新表仍然递增有序，可以利用尾插法建立单链表的方法，只是新表中的结点不用malloc，而只要从表LA和LB中选择合适的点插入新表LC即可。
算法：
typedef struct Node {
ElemType data;
struct Node * next; }Node,*LinkList;
LinkList MergeLinkList(LinkList LA,LinkList LB) {
Node *pa,*pb,*pc; LinkList LC;
/*pa和pb分别指向两个单链表LA和LB中的将要判断 的结点，pc初值为LC且pc始终指向LC的表尾*/ pa=LA->next; pb=LB->next; LC=LA;
LC->next=NULL; /*将LC初始置为空表*/ pc=LC; /*pc始终指向LC的表尾*/ /*当两表均未处理完时，选择较小者*/ while(pa!=NULL&&pb!=NULL) { if(pa->data<=pb->data) {pc->next=pa;pc=pc->next;pa=pa->next;} else {pc->next=pb;pc=pc->next;pb=pb->next;} }
if(pa==NULL)/*表B未处理完*/ pc->next=pb;
else /*表A未处理完*/ pc->next=pa;
free(LB); /*表C是以表A为基础，所以释放表B*/ return LC; }
2.3.3 循环链表
循环链表：循环链表是一个首尾相接的链表。
特点：将单链表最后一个结点的指针域由NULL改为指向头结
点或线性表中的第一个结点，就得到了单链表形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。 带头结点的循环链表的算法和带头结点的单链表的算法的区别仅在与算法中判别当前结点p是否为尾结点。单链表判别条件为
p!?NULLorp??next!?NULL，而循环单链表的判别条件为p!?Lorp??next!?L。
例题：有两个带头结点的循环单链表LA、LB，编写算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。
算法思想：先找到两个链表LA、LB的表尾，并分别由指针p，q指向它们，然后将第一个链表的尾与第二个链表的第一个结点链接起来，并修改第二表的表尾q，使它指向第一个表的头结点。 算法：
typedef struct Node
{
ElemType data;
struct Node * next; }Node,*LinkList;
LinkList merge_1(LinkList LA,LinkList LB) {
Node *p,*q; p=LA;q=LB;
/*寻找A的尾结点，并置为p*/ while(p->next!=LA) p=p->next;
/*寻找B的尾结点，并置为q*/ while(q->next!=LB) q=q->next;
/*修改A的尾指针，并使之为B的第一节点*/ p->next=LB->next;
/*修改B的尾指针，并使之为A的头结点*/ q->next=LA; free(LB); return LA; }
采用上面的方法，需要遍历链表，找到表尾，其执行时间为O(n)。 若循环单链表设置为尾指针表示，在实现上述合并时，无需循环遍历找尾结点，只需直接修改尾结点的指针域，其执行时间是O(1)。
算法：
typedef struct Node {
ElemType data;
struct Node * next; }Node,*LinkList;
LinkList merge_2(LinkList RA,LinkList LB) {
Node *p;
p=RA->next; /*记录A的头结点*/ RA->next=RB->next->next; free(RB->next); RB->next=p;
return RB; /*返回新循环链表的尾指针*/ }
2.3.4 双向链表
双向链表：给单链表的每个结点里再增加一个指向其前驱的指针域prior。双链表的结点的结构如下图：
前驱指针域 typedef struct DNode {
ElemType data;
struct DNode *prior,*next; }DNode,*DoubleList;
prior data next 数据域 后继指针域 双链表的结构定义如下：
设指针p指向双链表中某一点，则有下式成立：
1、双向链表
?p??prior??next??p??p??p??next??prior的前插操作
算法思想：欲在双向链表第i个结点之前插入一个新的结点，则指针的变化情况如下图：
算法：
typedef struct DNode {
ElemType data;
struct DNode *prior,*next; }DNode,*DoubleList;
int DlinkIns(DoubleList L,int i,ElemType e) {
DNode *p,*s; int k; if(i<=0) return ERROR; p=L;k=0;
while(p!=NULL&&k
if(p==NULL) {