目录
序言
设A B两个链表为带头结点的单链表，且AB升序，求AB的交集
题目与题目解析，做题步骤
完整代码
两个链表A B, 判断链表B是否为A的子序列
题目与题目解析，做题步骤
完整代码
归并两个带头结点有序链表
题目与题目解析，做题步骤
完整代码
序言
关于带头结点单链表的构造与创建，可以在博主主页搜索“详细解析单链表带头节点的结构体定义，普通单链表与有序单链表的创建等操作”，即可查看详情，在这篇博文中，我们就直接进入正题啦
正文
设A B两个链表为带头结点的单链表，且AB升序，求AB的交集
题目与题目解析，做题步骤
设A B两个链表为带头结点的单链表，且 A B升序，求A B的交集。
A B都有的元素 组成一个新链表C，原 A B不动 ，且C也要升序
eq:
A: 1 2 2 3 5 6
B: 1 1 1 2 2 3 (一样的取一个)
==>C: 1 2 3
dsave = 0
算法思路：
s1：创建一个新的头结点链表C （交集）
s2：找相同的点 （遍历A和B 找相同的点 相同且不重复 就插入到链表C 不相同 谁小就往后移）
s3：把相同的点加入到链表头结点
s4: 把新链表的头结点返回。
完整代码
/* common_of_lists:求两个链表的交集 @listA:链表A @listB:链表B 返回值： 交集链表C的头结点 */ List *common_of_lists(List *listA, List *listB) { ElemType dsave = 0; Node *pnew = NULL; // s1：创建一个新的头结点链表C （交集） List *listC = malloc(sizeof(*listC)); listC->first = NULL; listC->last = NULL; listC->NodeNum = 0; // s2：找相同的点 （遍历A和B 找相同的点 相同且不重复 就插入到链表C 不相同 谁小就往后移） Node *pa = listA->first; Node *pb = listB->first; while(pa && pb) { if(pa->data == pb->data)// s3：把相同的点加入到链表头结点 { if(pa->data != dsave)//如果该节点与上一个结点的值不重复 就添加到新的链表C中 { pnew = malloc(sizeof(*pnew)); pnew->data = pa->data; pnew->next = NULL; if(listC->first == NULL)//从无到有 { listC->first = pnew; listC->last = pnew; } else//从少到多尾插 { listC->last->next = pnew; listC->last = pnew; } listC->NodeNum++; dsave = pa->data; } pa = pa->next; pb = pb->next; } else if(pa->data < pb->data)//如果不相等 谁小往后走 升序，看后面有没有大一点的值 和现在的值相等 { pa = pa->next; } else { pb = pb->next; } } // s4: 把新链表的头结点返回。 return listC; }
两个链表A B, 判断链表B是否为A的子序列
题目与题目解析，做题步骤
两个链表A B, 判断链表B是否为A的子序列。
子序列：连续的一部分
是：返回1
不是： 返回0
A: 1 1 1 2 3 5 6
B: 1 1 2 3 5
==>OK
A: 1 1 2 1 5 5 5 3
B: 1 2 3
==>不ok
算法思路：
相等 则继续往下走遍历
不相等 B回到开头
长链A 定义一个起始位置 不相等则起始位置往后移一位。
完整代码
/* judge_sublist: 判断链表B是否是链表A的子序列 @listA: A链表 @listB: B链表 返回值： 是子序列 返回1 不是子序列 返回0 */ int judge_sublist(List *listA, List *listB) { Node *pa = listA->first;//pa链表A的遍历指针 Node *pb = listB->first;//pb链表B的遍历指针 Node *start_a = listA->first;//A链表的起始位置 while(pa && pb) { if(pa->data == pb->data)//相等则继续往下遍历 { pa = pa->next; pb = pb->next; } else//不相等 B回到起始位置 pa的位置往下走 { pb = listB->first;//pb回到开头 start_a = start_a->next;//pa的位置往后走 pa = start_a; } } if(pb == NULL) { return 1; } else { return 0; } }
归并两个带头结点有序链表
题目与题目解析，做题步骤
归并两个带头结点有序链表
合并两个有序的升序链表成一个升序链表
A:1 2 3 3 5 6
B:1 5 6
C=> 1 1 2 3 3 5 5 6 6
算法思路：
两两比较 取较小的 加入到新链表C中
step1: 创建一个带头结点的链表C
step2:两两比较，把较小的结点摘下来
step3： 把摘下来的结点 加入到链表C
step4： 返回链表C的头结点
完整代码
List *merge_two_lists(List *listA, List *listB) { //step1: 创建一个带头结点的链表C List *listC = malloc(sizeof(*listC)); listC->first = NULL; listC->last = NULL; listC->NodeNum = listA->NodeNum + listB->NodeNum; Node *pnew = NULL;//指向摘下来的那个结点 //step2:两两比较，把较小的结点摘下来 Node *pa = listA->first; Node *pb = listB->first; while(pa && pb) { if(pa->data < pb->data)//listA小 { pnew = pa; listA->first = listA->first->next; pa->next = NULL; } else//listB小 { pnew = pb; listB->first = listB->first->next; pb->next = NULL; } //step3： 把摘下来的结点 加入到链表C if(listC->first == NULL)//从无到有 { listC->first = pnew; listC->last = pnew; } else//从少到多 { listC->last->next = pnew; listC->last = pnew; } pa = listA->first; pb = listB->first; }//end while if(pa != NULL)//A链表有剩余 { listC->last->next = listA->first; listC->last = listA->last; } else//B链表有剩余 { listC->last->next = listB->first; listC->last = listB->last; } //step4： 返回链表C的头结点 return listC; }
