【数据结构】 合并两个非递减有序单链表为一个A-B的非递减有序单链表

题目

实现两个单链表La和Lb的相减链表LC，LC的元素为LA中有但LB中没有的元素。LA和LB都为非递减有序链表

分析

LC是LA和LB的相减链表，即LC= LA-LB，即LC里的元素是在LA的基础减去LB里也有的元素。比如LA的元素为1，3，5，7，9，LB的元素为2，4，5，7，9，那么LC的元素为1，3 。

解题思路

再重复一下我们的分析： LC是LA和LA的相减链表，即LC里的元素是在LA的基础减去LB里也有的元素。所以思路就是： 首先把LC指向LA。（“在LA的基础上”）遍历LA和LB链表，找到A∩B的元素，并删除LA相应的元素。（“减去LB里也有的元素”） 一般我们会先遍历LA，对于每个LA的元素都遍历一次LB，看是否有相等的元素删去。这样做法的时间复杂度是O(n²)。但由于LA和LB都是非递减有序的，我们可以优化一下，改成O(n)的做法。

优化

假设p为遍历LA的指针，q为遍历LB的指针。我们可以发现，由于我们整个操作都是在LA的基础上进行元素的删除，所以LA的每一个元素是必须要遍历一遍的。但由于LB是非递减序列，我们可以通过与LA元素的比较来确定ｑ指针的位置： p->data < q->data, 此时LA的元素 < LB的元素, 对于LA的下一个元素m, 此时LB的元素更大，不能确定LB前面有没有比m更小的数，所以应返回LB开头重新遍历。即q = LB->next。【LA：2( p)， 3，5，9，LB：1，3，4(q)，7】p->data > q->data，此时LA的元素 > LB的元素，对于LA的下一个元素m，此时LB的元素偏小，所以继续往后遍历LB即可。即q = q->next。【LA：2，3，5( p)，9，LB：1，3，4(q)，7】p->data == q->data，此时LA的元素 ==LB的元素, 将LA中的结点删掉，继续遍历LA，LB。即p = p->next, q = q->next。【LA：2，3( p)，5，9，LB：1，3(q)，4，7】

难点

可以发现，只有当p->data == q->data时，p才会往后走。后来写代码的时候发现出现死循环，因为LA走的还不够。当[ LA：2，3，5( p)，7，9，LB：1，3，4(q)，7] 时，我们会先执行上面的第2步，然后LB继续遍历，变成[ LA：2，3，5( p)，7，9，LB：1，3，4，7(q) ], 此时程序执行第1步，LB从头开始遍历，此后一直执行第2步，直到[ LA：2，3，5( p)，7，9，LB：1，3，4，7(q) ] ，陷入死循环。跳出死循环的方法是让p往前走一步。p往前走一步的前提是，当前p比q大且比q的下一个元素小，即p必然是在LC中的，可以往前走一步。

代码：

//初始化：pre指向LA当前结点的前一个结点，r指向LA当前结点的下一个结点。 while(p && q){ //遍历LA r = p->next; if(p->data < q->data){ //A<B q = LB->next; } else if(p->data > q->data){ //A>B q = q->next; //难点 if(p->data < q->data){//A<B的下一个，即A在两者间 pre = p; p = p->next; } } else if(p->data == q->data){ //A==B pre->next = r; Node *s; s=p; p = p->next; free(s); } }

我的代码：

//实现两个单链表La和Lb的相减链表Lc，Lc的元素为La中有但Lb中没有的元素。La和Lb都为非递减有序链表。 #include<stdio.h> #include<stdlib.h> typedef int Elem; typedef struct Node{ Elem data; struct Node *next; }*Linklist, Node; void Init(Linklist*); //初始化链表 void Create(Linklist); //创建单链表 void output(Linklist); //输出单链表 Linklist Merge(Linklist, Linklist); //合并两个单链表（A-B），并返回一个单链表 int main(){ system("color 3F"); Linklist LA, LB; //定义两个单链表 Init(&LA); //初始化两个单链表 Init(&LB); //注意此时传的是指针的地址（指针的指针），因为这样才能保存而不会随着函数消失。 printf("\t\t\t请输入单链表LA的元素（结束则输入-1）："); Create(LA); //创建两个单链表 printf("\t\t\t请输入单链表LB的元素（结束则输入-1）："); Create(LB); printf("\t\t\t此时LA单链表元素为："); output(LA); printf("\t\t\t此时LB单链表元素为："); output(LB); Linklist LC; //定义新的单链表 Init(&LC); //初始化 LC = Merge(LA, LB); //合并LA，LB两个单链表，返回合并后的链表为LC printf("\t\t\t合并后LC单链表元素为："); output(LC); } //初始化单链表 void Init(Linklist *L){ //注意此时参数是指针的指针，即指针的地址 *L = (Linklist)malloc(sizeof(Node)); (*L)->next = NULL; } //创建单链表 （尾插法建表） void Create(Linklist L){ //此时参数是单链表的头指针 Node *r, *s; int flag = 1; //设置一个标志，初值为1，当输入-1时，flag为0，建表结束 r = L; // r指针动态指向链表的当前表尾，以便于作尾插入，初值指向头结点 Elem c; //c为要插入的元素值 while(flag){ scanf("%d", &c); if(c!=-1){ s = (Linklist)malloc(sizeof(Node)); //s指针指向要插入的元素。每次都要给s分配空间。 s->data = c; r->next = s; r = s; } else{ flag = 0; r->next = NULL; //将最后一个结点的next链域置为空，表示链表的结束。 } } } //输出链表 void output(Linklist L){ Node *r; r = L->next; while(r){ printf("%d ", r->data); r = r->next; } printf("\n"); } /* LC= LA-LB，即LC里的元素是在LA的基础上减去LA里有而LB里也有的。 遍历LA，LB，但何时回到LB开头从头需要判断。 1.p->data < q->data，此时A<B，因为LB递增，所以不需要再遍历LB，而应返回LB开头重新遍历。 2.p->data > q->data， 此时A>B，因为LB递增，所以继续往后遍历LB即可。 3.p->data == q->data，此时A==B，则需要将A中结点删除掉，继续遍历LA。 */ Linklist Merge(Linklist LA, Linklist LB){ Linklist LC; LC = LA; Node *p, *q, *pre, *r; pre = LA; p = LA->next; q = LB->next; while(p && q){ //遍历LA r = p->next; if(p->data < q->data){ //A<B q = LB->next; } else if(p->data > q->data){ //A>B q = q->next; if(p->data < q->data){//A<B的下一个，即A在两者间 pre = p; p = p->next; } } else if(p->data == q->data){ //A==B pre->next = r; Node *s; s=p; p = p->next; free(s); } } free(LB); return LC; }