• 王道链表综合题(下)

    提示：心中有丘壑 眉目作山河

    文章目录

    第十七题

    请添加图片描述

    先谈

    先建立双向循环链表 然后使用两个指针，一个从前向后 一个从后向前 比较是否相等便可，注意本题使用栈消栈顶则较麻烦 因为总的个数可能是奇数个

    双链表头插法建立

    BiLNode* InitHeadBiList(){
	BiLNode* L=(BiLNode*)malloc(sizeof(BiLNode));
	L->next=L;
	L->pre=L; 	
	cout<<"请输入双向循环链表的值"<<endl;
	int input;
	while(scanf("%d",&input)!=EOF){
		BiLNode* cur=(BiLNode*)malloc(sizeof(BiLNode));
		cur->data=input;
		//下面来建立四条链 
		cur->pre=L->pre;
		cur->next=L;
		L->pre->next=cur;
		L->pre=cur;
	} 
	BiLNode* p=L->next;
	cout<<"此时双向循环链表是";
	while(p!=L){
		cout<<p->data<<" ";
		p=p->next;
	} 
	cout<<endl;
	//前面单链表中使用的都是头插法 这里使用尾插法，
	return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    解决17题代码

    void Solution17(BiLNode* L){
	BiLNode* p=L->next;
	BiLNode* q=L->pre;
	while(p->data==q->data&&p!=q&&p->next!=q){
		p=p->next;
		q=q->pre;
	}
	if(p==q){
		cout<<"此时链表对称";
	}
	else if(p->next==q){
		if(p->data==q->data){
			cout<<"此时链表对称"; 
		} 
		else{
			cout<<"此时链表不对称" ; 
		}
	}
	else {
		cout<<"此时链表并不对称";
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    第十八题

    请添加图片描述

    先谈

    找到h1的yi巴 然后将h2 接入即可

    代码

    void Solution18(LNode* &L1,LNode* &L2){
	//因为我这里不是两个循环链表 所以先造两个循环链表 
	LNode* tail1=L1;
	while(tail1->next){
		tail1=tail1->next;
	} 
	tail1->next=L1;
	LNode* tail2=L2;
	while(tail2->next){
		tail2=tail2->next;
	}
	tail2->next=L2;
	//以上完成两个循环链表的构建
	tail1=L1;
	while(tail1->next!=L1){
		tail1=tail1->next;
	} 
	tail2=L2;
	while(tail2->next!=L2){
		tail2=tail2->next;
	}
	tail1->next=L2->next;
	tail2->next=L1;
	//输出打印验证
	tail1=L1->next;
	while(tail1){
		cout<<tail1->data;
		tail1=tail1->next;
	} 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    运行截图

    至于为什么有零，是因为这里我使用的带头结点的循环链表
    请添加图片描述

    第十九题

    请添加图片描述

    先谈

    本题无非定义两个指针，一个用于保存最小值，一个用于遍历，然后在删除就可以了

    代码

    void Solution19(LNode* &L){
	LNode* tail=L->next;
	while(tail->next){
		tail=tail->next;
	} 
	tail->next=L;
	cout<<tail->data;
	LNode* p=L->next;
	LNode* q=L;
	LNode* Min=L;
	while(L->next!=L){ 
		p=L->next;
		Min=L;//定位到最小值的前一个结点 
		while(p->next!=L){//从头往后找一个最小值 
			 if(p->next->data<Min->next->data){
			 	Min=p;
			 }
			 p=p->next;
		}
		LNode* Del=Min->next;cout<<"此时删除的节点是"<<Min->next->data<<" "<<endl; 
		Min->next=Min->next->next;
		free(Del);Del=NULL;
	} 
	free(L);
	L=NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    运行截图

    请添加图片描述

    第二十题

    请添加图片描述

    先谈

    首先我们需要通过一个指针先找到这个x 然后给他的freq域加一 然后判断此时这个x 应处的位置，判断与当前位置是否一致 若是不一致则进行删除插入

    头插法建立双向链表

    Freq* InitFreqBiList(){
	Freq* L=(Freq*)malloc(sizeof(Freq));
	L->next=NULL;
	L->pre=NULL; 	
	cout<<"请输入双向链表的值"<<endl;
	int input;
	while(scanf("%d",&input)!=EOF){
		Freq* cur=(Freq*)malloc(sizeof(Freq));
		cur->data=input;
		//下面来建立四条链 
		cur->pre=L;
		cur->next=L->next;
		if(L->next==NULL){
			
		}
		else{
			L->next->pre=cur;	
		}
		L->next=cur;
	} 
	Freq* p=L->next;
	cout<<"此时双向链表是";
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	} 
	cout<<endl;
	return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    20题代码

    Freq* Solution20(Freq* &L,int x){
	Freq* p=L->next;
	Freq* flag=L;
	while(p!=NULL){
		if(p->data==x){
			p->freq+=1;
			flag=p;
			break;
		}
		p=p->next;
	}
	//然后按照freq的值进行插入 从p的位置开始向前找
	while(p!=NULL){
		if(p->freq>flag->freq||p->pre==NULL){//插入p的后面位置
			cout<<p->freq<<" "<<flag->freq<<" "<<endl; 
			Freq* OldFreq=flag; 
			//删除
			flag->pre->next=flag->next;
			flag->next->pre=flag->pre;
			//插入
			OldFreq->next=p->next;
			OldFreq->pre=p;
			p->next->pre=OldFreq;
			p->next=OldFreq;
			break;
		}
		p=p->pre; 
	} 
	p=L->next;
	while(p){
		cout<<p->data<<" ";
		p=p->next; 
	}
	cout<<endl;
	cout<<"此时数组中的频率是";
	p=L->next;
	while(p){
		cout<<p->freq<<" ";
		p=p->next; 
	}
	cout<<endl; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    运行截图

    请添加图片描述

    第二十一题

    请添加图片描述

    先谈

    首先自然是暴力算法，使用两个指针，一个固定，一个用于遍历，判断两个是否会相等
    第二种就是使用快慢指针的方式，一个每一次移动两个位置，一个每一次移动一个位置，当他们进入环中的时候，因为步子不一样，导致最后一定会相遇，并且相遇的时候，solw 指针移动的不足一圈，有人可能会想为什么不足一圈，因为若是slow与quick 同样起点一起移动 等slow移动到终点的时候，qucik 一定移动了两圈， 这两圈也就导致无论圈中结点是奇数或者是偶数都一定会相遇，并且quick 本来就比slow先进入 环中
    请添加图片描述

    代码

    注意设置快慢指针的时候，要注意都是指向表头的，但是若是开始的指向不一样 得到的关系也就不一样

    LNode* Solution21(LNode* &L){
	if(L->next==NULL){
		cout<<"此时链表为空"<<endl; 
	}
	//首先构造一个带环的L
	cout<<"你想将第几个结点设置为环的入口"<<endl;
	int input;cin>>input;
	LNode* tail=L->next;
	LNode* enter;
	while(tail->next){
		if(!(--input)){
			enter=tail;
		}
		tail=tail->next;
	}
	tail->next=enter; 
	//完成带环链表的构建
	LNode* solw=L;
	LNode* quick=L;
	do{
		solw=solw->next;
		quick=quick->next->next;	
	}while(solw!=quick);
	return solw; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    运行截图

    请添加图片描述

    第二十二题

    请添加图片描述

    先谈

    第一想法将链表反转，找到之后再反转，
    第二想法就是将链表中的数据存放在容器中，然后直接查找就可
    第三个方法是先使用一个指针探路，然后知道链表的长度 然后再重现移动n-r个结点即可
    王道上的方法：先使用一个指针移动k个单位 再使用一个指针从头开始移动 当第一个指针移动到最后一个位置的时候，刚才那个从头移动的指针 此时的位置正好是倒数第K个位置，

    代码

    void Solution22(LNode* &L){
	cout<<"请输入你要查找倒数第几个上的元素"<<endl;
	int input;cin>>input; int x=input;
	LNode* quick=L->next;
	LNode* slow=L->next;
	while(--input){
		quick=quick->next;
	}
	while(quick->next){
		quick=quick->next;
		slow=slow->next;
	}
	cout<<"倒数第"<<x<<"上的元素是"<<slow->data<<endl; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    运行截图

    请添加图片描述

    第二十三题

    请添加图片描述

    先谈

    这个不就是寻找两个链表的公共结点？
    有兴趣的可以看这一篇中的第八题使用栈结构，这里我们使用一个新的方法快慢指针的方式 首先使得一个指针先移动Len1-Len2个长度 然后两个再一起移动 然后比较两个指针指向是否相等来判断什么位置是公共结点

    代码

    LNode* Solution23(LNode* &L1,LNode* &L2){
	int input;LNode* p=L2;LNode* q=L1; LNode* L3=NULL;
	cout<<"请问你要将L1接到L2的第几个位置之前(位置从1开始)"<<endl;
	cin>>input;
	while(input--){
		p=p->next;
	}
	while(q->next){
		q=q->next;
	}
	q->next=p;
	cout<<"此时拼接之后的链表L1是";
	q=L1;
	while(q->next){
		cout<<q->next->data<<" ";
		q=q->next;
	}
	cout<<endl;
	//此上已经构造两个链表具有公共节点
	//首先需要知道L1的长度 然后需要知道L2的长度
	p=L1->next;int len1=1;
	q=L2->next;int len2=1;
	while(p->next){
		p=p->next;
		len1+=1;
	} 
	while(q->next){
		q=q->next;
		len2+=1;
	}
	//先让长的移|len1-len2|;
	p=L1->next;q=L2->next;
	if(len1>len2){
		int margin=len1-len2;
		while(margin--){
			p=p->next;
		}
		while(p!=q){
			p=p->next;
			q=q->next;
		}
	}
	else{
		int margin=len2-len1;
		while(margin--){
			q=q->next;
		}
		while(p!=q){
			p=p->next;
			q=q->next;
		}
	}
	L3=p;
	return L3;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    运行效果

    请添加图片描述

    第二十四题

    请添加图片描述

    先谈

    第一想法是使用一个数组，若是其中已经有元素则不删除 若是其中已经有元素则删除

    代码

    void Solution24(LNode* &L){
	int a[100]={0};
	LNode* p=L; 
	while(p->next){
		if(a[abs(p->next->data)]!=0){
			LNode* Oldp=p->next;
			p->next=p->next->next;
			free(Oldp);
		}
		else{
			a[p->next->data]=1;
			p=p->next;
		}
	}
	PrintHead(L);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    运行截图

    请添加图片描述

    第二十五题

    请添加图片描述

    先谈

    首先看到奇数项是递增的 而偶数项是递减的 所以我想可能需要反转数组，这里反转后一部分的链表 然后将An插入A1 的后面，将An-1插入到A2 后面 直到后一部分遍历结束

    代码

    void Solution25(LNode* &L){
	LNode* p=L->next;
	LNode* q=L->next;
	//首先需要知道链表的长度
	int len=1;
	while(p->next){
		len+=1;
		p=p->next;
	}
	int mid=len-len/2;
	LNode* MidNode=L->next;
	cout<<"链表的长度是"<<len<<endl;
	//找到中间结点的位置
	while(--mid){ 
		q=q->next;
	} 
	MidNode=q;
	cout<<"中间结点的值是"<<MidNode->data<<endl;
	//将中间结点之后的结点反转
	LNode* r=MidNode->next->next;
	p=MidNode->next;
	q=MidNode->next;
	while(r){
		q=r;
		r=q->next;
		q->next=p;
		p=q;	
	};
	MidNode->next->next=NULL;
	MidNode->next=p;
	PrintHead(L); 
	//将后半部分的插入到前半部分中
	p=L->next; 
	while(MidNode->next){
		//删除后半部分的第一个结点 
		LNode* cur=MidNode->next;
		MidNode->next=MidNode->next->next;
		//将结点插入前半部分p的后面； 
		cur->next=p->next;
		p->next=cur;
		//将p向后移动两个单位 
		p=p->next->next;
	} 
	PrintHead(L); 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    运行截图

    请添加图片描述

    可执行代码汇总

    #include
using namespace std;
#define F(i,m,n) for(int i=m;i<n;i++)
#define ElemType int
typedef struct LNode{
	ElemType data;
	struct LNode* next;
}LNode;
typedef struct BiLNode{
	ElemType data;
	struct BiLNode* pre;
	struct BiLNode* next; 
}BiLNode;
typedef struct Freq{
	ElemType data;
	struct Freq* pre;
	struct Freq* next;
	int freq=0; 
}Freq; 
void Print(LNode* L){
	cout<<"此时的链表是"<<endl;
	if(L==NULL){
		cout<<"此时是空表"<<endl;
		return;
	}
	for(LNode* i=L;i!=NULL;i=i->next){
		cout<<i->data<<" ";
	} 
	cout<<endl;
}
void PrintHead(LNode* L){
	cout<<"此时的链表是"<<endl;
	if(L->next==NULL){
		cout<<"此时是空表"<<endl;
		return;
	}
	for(LNode* i=L->next;i!=NULL;i=i->next){
		cout<<i->data<<" ";
	} 
	cout<<endl;
}
LNode* InitHeadList(){
	cout<<"请输入链表的值"<<endl;
	LNode* L=(LNode*)malloc(sizeof(LNode));
	L->data=0;//头结点这里可以存放链表的长度 
	L->next=NULL;
	int input;
	while(scanf("%d",&input)!=EOF){
		LNode* cur=(LNode*)malloc(sizeof(LNode));
		cur->data=input;
		cur->next=L->next;
		L->next=cur;
	}
	PrintHead(L);
	return L;
}
Freq* InitFreqBiList(){
	Freq* L=(Freq*)malloc(sizeof(Freq));
	L->next=NULL;
	L->pre=NULL; 	
	cout<<"请输入双向链表的值"<<endl;
	int input;
	while(scanf("%d",&input)!=EOF){
		Freq* cur=(Freq*)malloc(sizeof(Freq));
		cur->data=input;
		//下面来建立四条链 
		cur->pre=L;
		cur->freq=0;
		cur->next=L->next;
		if(L->next==NULL){
			
		}
		else{
			L->next->pre=cur;	
		}
		L->next=cur;
	} 
	Freq* p=L->next;
	cout<<"此时双向链表是";
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	} 
	cout<<endl;
	return L;
}
BiLNode* InitHeadBiList(){
	BiLNode* L=(BiLNode*)malloc(sizeof(BiLNode));
	L->next=L;
	L->pre=L; 	
	cout<<"请输入双向循环链表的值"<<endl;
	int input;
	while(scanf("%d",&input)!=EOF){
		BiLNode* cur=(BiLNode*)malloc(sizeof(BiLNode));
		cur->data=input;
		//下面来建立四条链 
		cur->pre=L->pre;
		cur->next=L;
		L->pre->next=cur;
		L->pre=cur;
	} 
	BiLNode* p=L->next;
	cout<<"此时双向循环链表是";
	while(p!=L){
		cout<<p->data<<" ";
		p=p->next;
	} 
	cout<<endl;
	//前面单链表中使用的都是头插法 这里使用尾插法，
	return L;
}
LNode* InitList(){
	cout<<"请输入链表的值"<<endl;
	int input; LNode* L=NULL;
	while(scanf("%d",&input)!=EOF){
		LNode* cur=(LNode*)malloc(sizeof(LNode));
		cur->next=L;
		cur->data=input;
		L=cur;
	}
	Print(L);
	return L;
}
void Solution17(BiLNode* L){
	BiLNode* p=L->next;
	BiLNode* q=L->pre;
	while(p->data==q->data&&p!=q&&p->next!=q){
		p=p->next;
		q=q->pre;
	}
	if(p==q){
		cout<<"此时链表对称";
	}
	else if(p->next==q){
		if(p->data==q->data){
			cout<<"此时链表对称"; 
		} 
		else{
			cout<<"此时链表不对称" ; 
		}
	}
	else {
		cout<<"此时链表并不对称";
	}
}
void Solution18(LNode* &L1,LNode* &L2){
	//因为我这里不是两个循环链表 所以先造两个循环链表 
	LNode* tail1=L1;
	while(tail1->next){
		tail1=tail1->next;
	} 
	tail1->next=L1;
	LNode* tail2=L2;
	while(tail2->next){
		tail2=tail2->next;
	}
	tail2->next=L2;
	//以上完成两个循环链表的构建
	tail1=L1;
	while(tail1->next!=L1){
		tail1=tail1->next;
	} 
	tail2=L2;
	while(tail2->next!=L2){
		tail2=tail2->next;
	}
	tail1->next=L2->next;
	tail2->next=L1;
	//输出打印验证
	tail1=L1->next;
	while(tail1){
		cout<<tail1->data;
		tail1=tail1->next;
	} 
}
void Solution19(LNode* &L){
	LNode* tail=L->next;
	while(tail->next){
		tail=tail->next;
	} 
	tail->next=L;
	cout<<tail->data;
	LNode* p=L->next;
	LNode* q=L;
	LNode* Min=L;
	while(L->next!=L){ 
		p=L->next;
		Min=L;//定位到最小值的前一个结点 
		while(p->next!=L){//从头往后找一个最小值 
			 if(p->next->data<Min->next->data){
			 	Min=p;
			 }
			 p=p->next;
		}
		LNode* Del=Min->next;cout<<"此时删除的节点是"<<Min->next->data<<" "<<endl; 
		Min->next=Min->next->next;
		free(Del);Del=NULL;
	} 
	free(L);
	L=NULL;
}
Freq* Solution20(Freq* &L,int x){
	Freq* p=L->next;
	Freq* flag=L;
	while(p!=NULL){
		if(p->data==x){
			p->freq+=1;
			flag=p;
			break;
		}
		p=p->next;
	}
	//然后按照freq的值进行插入 从p的位置开始向前找
	while(p!=NULL){
		if(p->freq>flag->freq||p->pre==NULL){//插入p的后面位置
			cout<<p->freq<<" "<<flag->freq<<" "<<endl; 
			Freq* OldFreq=flag; 
			//删除
			flag->pre->next=flag->next;
			flag->next->pre=flag->pre;
			//插入
			OldFreq->next=p->next;
			OldFreq->pre=p;
			p->next->pre=OldFreq;
			p->next=OldFreq;
			break;
		}
		p=p->pre; 
	} 
	p=L->next;
	while(p){
		cout<<p->data<<" ";
		p=p->next; 
	}
	cout<<endl;
	cout<<"此时数组中的频率是";
	p=L->next;
	while(p){
		cout<<p->freq<<" ";
		p=p->next; 
	}
	cout<<endl; 
}
LNode* Solution21(LNode* &L){
	if(L->next==NULL){
		cout<<"此时链表为空"<<endl; 
	}
	//首先构造一个带环的L
	cout<<"你想将第几个结点设置为环的入口"<<endl;
	int input;cin>>input;
	LNode* tail=L->next;
	LNode* enter;
	while(tail->next){
		if(!(--input)){
			enter=tail;
		}
		tail=tail->next;
	}
	tail->next=enter; 
	//完成带环链表的构建
	LNode* solw=L;
	LNode* quick=L;
	do{
		solw=solw->next;
		quick=quick->next->next;	
	}while(solw!=quick);
	return solw; 
}
void Solution22(LNode* &L){
	cout<<"请输入你要查找倒数第几个上的元素"<<endl;
	int input;cin>>input; int x=input;
	LNode* quick=L->next;
	LNode* slow=L->next;
	while(--input){
		quick=quick->next;
	}
	while(quick->next){
		quick=quick->next;
		slow=slow->next;
	}
	cout<<"倒数第"<<x<<"上的元素是"<<slow->data<<endl; 
}
LNode* Solution23(LNode* &L1,LNode* &L2){
	int input;LNode* p=L2;LNode* q=L1; LNode* L3=NULL;
	cout<<"请问你要将L1接到L2的第几个位置之前(位置从1开始)"<<endl;
	cin>>input;
	while(input--){
		p=p->next;
	}
	while(q->next){
		q=q->next;
	}
	q->next=p;
	cout<<"此时拼接之后的链表L1是";
	q=L1;
	while(q->next){
		cout<<q->next->data<<" ";
		q=q->next;
	}
	cout<<endl;
	//此上已经构造两个链表具有公共节点
	//首先需要知道L1的长度 然后需要知道L2的长度
	p=L1->next;int len1=1;
	q=L2->next;int len2=1;
	while(p->next){
		p=p->next;
		len1+=1;
	} 
	while(q->next){
		q=q->next;
		len2+=1;
	}
	//先让长的移|len1-len2|;
	p=L1->next;q=L2->next;
	if(len1>len2){
		int margin=len1-len2;
		while(margin--){
			p=p->next;
		}
		while(p!=q){
			p=p->next;
			q=q->next;
		}
	}
	else{
		int margin=len2-len1;
		while(margin--){
			q=q->next;
		}
		while(p!=q){
			p=p->next;
			q=q->next;
		}
	}
	L3=p;
	return L3;
}
void Solution24(LNode* &L){
	int a[100]={0};
	LNode* p=L; 
	while(p->next){
		if(a[abs(p->next->data)]!=0){
			LNode* Oldp=p->next;
			p->next=p->next->next;
			free(Oldp);
		}
		else{
			a[p->next->data]=1;
			p=p->next;
		}
	}
	PrintHead(L);
}
void Solution25(LNode* &L){
	LNode* p=L->next;
	LNode* q=L->next;
	//首先需要知道链表的长度
	int len=1;
	while(p->next){
		len+=1;
		p=p->next;
	}
	int mid=len-len/2;
	LNode* MidNode=L->next;
	cout<<"链表的长度是"<<len<<endl;
	//找到中间结点的位置
	while(--mid){ 
		q=q->next;
	} 
	MidNode=q;
	cout<<"中间结点的值是"<<MidNode->data<<endl;
	//将中间结点之后的结点反转
	LNode* r=MidNode->next->next;
	p=MidNode->next;
	q=MidNode->next;
	while(r){
		q=r;
		r=q->next;
		q->next=p;
		p=q;	
	};
	MidNode->next->next=NULL;
	MidNode->next=p;
	PrintHead(L); 
	//将后半部分的插入到前半部分中
	p=L->next; 
	while(MidNode->next){
		//删除后半部分的第一个结点 
		LNode* cur=MidNode->next;
		MidNode->next=MidNode->next->next;
		//将结点插入前半部分p的后面； 
		cur->next=p->next;
		p->next=cur;
		//将p向后移动两个单位 
		p=p->next->next;
	} 
	PrintHead(L); 
}
void Menu(){
	int choice;
	cout<<"请输入你要解决第几题"<<endl;
	cin>>choice;
	switch(choice){
		case 17:{
			BiLNode* L=InitHeadBiList();
			Solution17(L);
			break;
		}
		case 18:{
			LNode* L1=InitHeadList();
			LNode* L2=InitHeadList();
			Solution18(L1,L2);
			break;
		}
		case 19:{
			LNode* L=InitHeadList();
			Solution19(L); 
			break;
		}
		case 20:{
			int input;
			Freq* L=InitFreqBiList();
			while(1){
				int choice;
				cout<<"若是输入请输入1"<<endl;
				cin>>choice;
				switch(choice){
					case 1:{
						cout<<"请输入你要查找的值"<<endl;
						cin>>input;
						Solution20(L,input);
						break;
					}
					default:{
						exit(0); 
						break;
					}
				} 
			}
		}
		case 21:{
			LNode* L=InitHeadList();
			LNode* cur=Solution21(L); 
			cout<<"此时环的入口是"<<cur->data;			
			break;
		}
		case 22:{
			LNode* L=InitHeadList();
			Solution22(L); 			
			break;
		}
		case 23:{
			LNode* L1;LNode* L2;LNode* L3;
			L1=InitHeadList();
			L2=InitHeadList();
			L3=Solution23(L1,L2);
			Print(L3); 
			break;
		}
		case 24:{
			LNode* L=InitHeadList();
			Solution24(L); 	
			break;
		}
		case 25:{
			LNode* L=InitHeadList();
			Solution25(L); 			
			break;
		}
	}
}
int main(){
	Menu();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443
    • 444
    • 445
    • 446
    • 447
    • 448
    • 449
    • 450
    • 451
    • 452
    • 453
    • 454
    • 455
    • 456
    • 457
    • 458
    • 459
    • 460
    • 461
    • 462
    • 463
    • 464
    • 465
    • 466
    • 467
    • 468
    • 469
    • 470
    • 471
    • 472
    • 473
    • 474
  • 相关阅读:
    【Java】三种不同的方式实现用户登录
    Sqoop的介绍和安装
    C++必修：从C到C++的过渡(下）
    vs2019快捷键注释不起作用
    C语言 深入探究C语言中的文件操作
    【C++】运算符重载 ⑭ ( 逻辑与 && 运算符重载 | 逻辑或 || 运算符重载 | 完整代码示例 )
    代码随想录算法训练营第三十一天 | 理论基础，455.分发饼干，376. 摆动序列，53. 最大子序和
    【论文阅读】基于隐蔽带宽的汽车控制网络鲁棒认证（一）
    Presto 之 explain and explain analyze的实现
    科技云报道：全球勒索攻击创历史新高，如何建立网络安全的防线？
  • 原文地址：https://blog.csdn.net/qq_56012214/article/details/126028179