1.将两个递增的有序链表合并成一个递增的有序链表？[去重 + 不开辟新空间]
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){
pa=La->next; pb=Lb->next; //初始化第一个节点
Lc=pc=La; //La节点作为Lc头结点
while(pa && pb){
//没到表尾部
if(pa->data<pb->data){
//将pa插入pc后面，pa后移
pc->next=pa;
pc=pa;
pa=pa->next;
}else if(pa->data>pb->data){
//将pb插入pc后面，pb后移
pc->next=pb;
pc=pb;
pb=pb->next;
}else{
//相等pa插入pc后，删除pb
pc->next=pa;
pc=pa;
pa=pa->next;
q=pb->next;
delete pb;
pb=q;
}
}
pc->next=pa?pa:pb; //插入剩余段
delete Lb;
}
2.将两个递增的有序链表合并成一个递减的有序链表？[不开辟新空间]
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){
pa=La->next; pb=Lb->next; //初始化第一个节点
Lc=pc=La; Lc->next=NULL;
while(pa || pb){
if(!pa) {
//La空，q指向pb，pb后移
q=pb;
pb=pb->next;
}else if(!pb){
//Lb空，q指向pa，pa后移
q=pa;
qa=qa->next;
}else if(pa->data<pb->data){
q=pa;
pa=pa->next;
}else{
q=pb;
pb=pb->next;
}
q->next=Lc->next; //q指向Lc下一个节点，反之
Lc->next=q;
}
delete Lb;
}
3.两个递增链表A、B，求A∩B的结果存放在A中？
void Mix(LinkList &La,LinkList &Lb,LinkList &Lc){
pa=La->next; pb=Lb->next; //初始化第一个节点
Lc=pc=La;
while(pa && pb){
if(pa->data==pb->data){
//交集加入Lc
pc->next=pa;
pc=pa;
pa=pa->next;
q=pb; pb=pb->next; delete q;
}else if(pa->data<pb->data){
q=pa; pa=pa->next; delete q;
}else{
q=pb; pb=pb->next; delete q;
}
}
while(pa){
q=pa; pa=pa->next; delete q; } //释放pa节点
while(pb){
q=pb; pb=pb->next; delete q; } //释放pb节点
pc->next=NULL; //链表尾部结束
delete Lb;
}
4.两个递增链表A、B，求A-B的结果、并返回元素个数？
void Different(LinkList &La,LinkList &Lb,int &n){
pa=La->next; pb=Lb->next;
pre=La; //pre为pa前驱
while(pa && pb){
if(pa->data<pb->data){
//pa后移
pre=pa;
pa=pa->next;
*n++;
}else if(pa->data>pb->data) pb=pb->next; //q后移
else{
//相等就要删除pa
pre->next=pa->next; //前驱后移到当前的下一个
q=pa; pa=pa->next; delete q; //删除当前节点
}
}
}
5.将带头结点的A链表，分成B、C两个链表？[B中元素小于0 + C中元素大于0]
void Dis(LinkList A){
B=A; B->next=NULL; //B初始化
C=new LinkList(); C->next=NULL;
p=A->next;
while(p!=NULL){
r=p->next; //暂存p的后继
if(p->data<0){
//存入b 前插
p->next=B->next;
B->next=p;
}else{
p->next=C->next; //存入c 前插
C->next=p;
}
p=r; //指向待处理节点
}
}
6.遍历链表求值最大的节点？
int Maxm(LinkList L){
if(L->next==NULL) return NULL;
maxn=L->next; //假设第一个节点为最大值
p=L->next->next; //从第二个节点开始遍历
while(p!=NULL){
if(p->data>maxn->data) maxn=p; //大于当前最大值，重新复制
p=p->next;
}
return maxn->data;
}
7.遍历链表，反转链表？
void Reverse(LinkList &L){
p=L->next; L->next=NULL; //逆置带头节点的L
while(p){
q=p->next;
p->next=L->next;
L->next=p;
p=q;
}
}
8.删除递增链表L中，大于mink且小maxk的元素？
void Delete(LinkList &L,int mink,int maxk){
p=L->next;
while(p && p->data<=mink){
pre=p; p=p->next; //pre为第一个大于mink的指针
}
if(p){
while(p && p<maxk) p=p->next; //p为第一个大于maxk的指针
q=pre->next; pre->next=p; //看不懂
while(q!=p){
xnx=q->next; delete q; q=xnx; //删除之间的节点
}
}
}
转载：https://blog.csdn.net/xg987599519/article/details/112000274
查看评论