路漫漫其修远兮,吾将上下而求索
1.应该很容易想到使用两个指针,一一对应看位置是否相等,然后来确定是否是公共结点,但是这个时间复杂度会达到O(n2) 那么2.我们想一想其他的方法,即如果两个链表若是有公共结点之后,公共结点之后的位置信息自然也一样的,所以就有另外一个想法就是将位置信息存放到栈中,
3.第三种就是使用王道上面的方法,让长度长一点的链表先移动(Len1-len2) 之后两个链表再一起移动 判断指向的是否是同一个位置就可
这里我们写第二种
LNode* Solution8(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;
//此上已经构造两个链表具有公共节点
stack<LNode*> S1; stack<LNode*> S2;
p=L1->next;q=L2->next;
while(p){
S1.push(p);
p=p->next;
}
while(q){
S2.push(q);
q=q->next;
}
while(S1.top()==S2.top()){
L3=S1.top();
S1.pop();
S2.pop();
}
return L3;
}
就跟上面第六题相同,但是上面第六题我们使用的是一个赋值空间,这里要求不能使用辅助空间,其实思想就是插入排序 再用两个指针一个释放 一个防止丢失便可,或者使用的就是每一个从链表中找一个最小值,然后输出 释放就可以
void Solution9(LNode* &L){
if(L->next==NULL){
return;
}
LNode* p=L;//p用来确定遍历多少次
cout<<"此时的从小到大的输出顺序是";
while(p->next!=NULL){
int min=L->next->data;
LNode* CurMin=L;
for(LNode* cur=L->next;cur->next!=NULL;cur=cur->next){
if(cur->next->data<min){
min=cur->next->data;
CurMin=cur;
}
}
LNode* OldCurMin=CurMin->next;
CurMin->next=CurMin->next->next;
free(OldCurMin);
cout<<min<<" ";
}
cout<<endl;
}
既然对空间没有要求 就将奇数项放到数组中,偶数项也放在另外一个数组中 最后再将数组放在链表中,然后将前一部分的最后一个指针赋值为NULL便可
void Solution10(LNode* &L){
LNode* L2;LNode* OldL;
LNode* p=L->next;
queue<int> Q1;
queue<int> Q2;
while(p){
Q1.push(p->data);
p=p->next;
if(p){
Q2.push(p->data);
p=p->next;
}
}
p=L->next;
while(p){
while(!Q1.empty()){
p->data=Q1.front();
Q1.pop();
OldL=p;
p=p->next;
}
L2=p;
while(!Q2.empty()){
p->data=Q2.front();
Q2.pop();
p=p->next;
}
}
OldL->next=NULL;
cout<<"此时第一个链表是"<<endl;
PrintHead(L);
cout<<"此时第二个链表是"<<endl;
Print(L2);
}
使用两个指针 分别标记头和尾,然后遍历链表,对头指针指向的使用尾插法,对尾指针指向的使用头插法,然后你发现其实本题中,你只需对其中2 4 6… 这些b 尾插到最后一个元素便可,其实本题若是严谨一些 是否要考虑数据元素个数的奇偶性 也就会导分链的时候有所不同 ,这里我们只考虑数据元素的个数为偶数的时候
void Insert(LNode* &L,LNode* &L2){//给定两个结点 将第二个结点插入到第一个结点之后
L2->next=L->next;
L->next=L2;
}
void Delete(LNode* &L){//给定一个结点删除它的后继结点
if(L->next==NULL){
return ;
}
L->next=L->next->next;
return ;
}
void Solution11(LNode* &L){
if(L->next==NULL){
cout<<"此时是空表"<<endl;
return;
}
LNode* p=L->next;//用于遍历链表
LNode* tail=L;
while(tail->next){//来找尾指针
tail=tail->next;
}
LNode* cur=L->next->next;//对链表的偶数项进行遍历
LNode* PreCur=L->next;//用于保存cur指针的前驱 防止断链
while(cur!=tail){
Delete(PreCur);
PreCur=cur->next;
Insert(tail,cur);
cur=PreCur->next;
}
PreCur->next=NULL;
Print(tail);
PrintHead(L);
}
本题可以使用两个指针,一个指向单链表中第一个元素 一个用于遍历链表,然后再释放后后面的空间即可
void Solution12(LNode* &L){
if(L->next==NULL){
cout<<"此时链表是空"<<endl;
}
LNode* p=L->next;
LNode* q=L->next;
while(q){
if(q->data!=p->data){
p->next->data=q->data;
p=p->next;
}
q=q->next;
}
//释放p之后的空间
q=p->next;
while(q){
LNode* Oldq=q->next;
free(q);
q=Oldq;
}
p->next=NULL;
PrintHead(L);
}
1。这个题最简单的方法就是将两个链表中的数据都放在容器中,然后再将容器中的数 放回到链表中,
2.或者就是元素对比 将一个链表中的结点不停的插入到另外一个链表中 最后再反转链表即可
LNode* Solution13(LNode* &L1,LNode* &L2){
LNode* p=L1;
LNode* q=L2;
LNode* Oldq;
while(q->next!=NULL&&p->next!=NULL){
if(q->next->data<=p->next->data){
//将q的后一个结点插入到p之后
Oldq=q->next;
q->next=q->next->next;
Oldq->next=p->next;
p->next=Oldq;
}
else{
p=p->next;
}
}
if(p->next==NULL){
p->next=q->next;
}
PrintHead(L1);
//接下来原地反转数组便可
if(L1->next->next==NULL){
return L1;
}
p=L1->next;
q=p->next;
LNode* r=q;
LNode* tail=p;
while(r){
r=q->next;
q->next=p;
p=q;
q=r;
}
L1->next=p;
tail->next=NULL;
PrintHead(L1);
}
使用两个指针p q,分别指向两个链表, 若是p的数据域等于q的数据域,则两个指针都向后移动,否则则小的指针向后移动 直到一个链表为空即可
void Solution14(LNode* &L1,LNode* &L2){
LNode* p=L1->next;LNode* q=L2->next;
LNode* L3=(LNode*)malloc(sizeof(LNode));//重新定义的一个新链表
LNode* tail=L3;//新链表的尾指针
while(p&&q){
if(p->data==q->data){
LNode* cur=(LNode*)malloc(sizeof(LNode));
cur->data=p->data;
cur->next=NULL;
tail->next=cur;
tail=tail->next;
p=p->next;
q=q->next;
}
else if(p->data<q->data){
p=p->next;
}
else{
q=q->next;
}
}
PrintHead(L3);
}
跟上题有点像 不过不是存放于新链表中 而是存放于L1 中,本题中需要三个指针 p q 的作用与上文是一样的,但是还需要一个r 指针 作用是标记此时L1中要进行数据交换的位置,有人可能会想冒然的进行数据交换是否会发生数据的覆盖导致L1数据丢失,这里告诉你不会的,因为若是修改数据 自然L1 p也是向后移动的, r绝对不会超过p
void Solution15(LNode* &L1,LNode* &L2){
LNode* p=L1->next;LNode* q=L2->next;
LNode* r=L1;
while(p&&q){
if(p->data==q->data){
r->next->data=p->data;
p=p->next;
q=q->next;
r=r->next;
}
else if(p->data<q->data){
p=p->next;
}
else{
q=q->next;
}
}
r->next=NULL;
PrintHead(L1);
}
1, 就如同模式匹配中一样,这里也是也是同样的可以使用暴力算法,定义两个指针,一个一个移动,若是发生失配 则p 指针移动到本次循环的开始位置,q指针依然从第一个数据开始,
2,有兴趣且有时间建议阅读这一篇MKP算法 这个题就可将数据先分别放入两个数组中,然后使用KMP进行模式匹配, 这里我们使用KMP 难度是有的
void GetNext(vector<int> V,int next[]){
next[1]=0;//相当于一个标志位
int i=1;//i用来指向第二个字符
int j=0;//j的指向要比i小
while(i<V.size()){
if(j==0||V[i-1]==V[j-1]){
++i;++j;
next[i]=j;
}
else{
j=next[j];
}
}
}
int KMP(vector<int> V1,vector<int> V2,int next[]){
int i= 1, j= 1;
while (i<=V1.size()&&j<=V2.size()){//因为表示的是位置 所以认为需要比对到=
if (j == 0 || V1[i-1]== V2[j-1]){
++i; ++j;
}
else
j=next[j];
}
if (j >V2.size())//因为是位置 这里需要> 单纯的等于可能不行
return i - V2.size();
else
return 0;
}
void Solution16(LNode* L1,LNode* L2){
LNode* p=L1->next;
LNode* q=L2->next;
vector<int> V1;
vector<int> V2;
while(p){
V1.push_back(p->data);
p=p->next;
}
while(q){
V2.push_back(q->data);
q=q->next;
}
int next[V2.size()+1];
GetNext(V2,next);
if(KMP(V1,V2,next)>0){
cout<<"此时能匹配并且位置是"<<KMP(V1,V2,next)<<endl;
}
else{
cout<<"此时不能模式匹配"<<endl;
}
}
#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;
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;
}
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;
}
LNode* Solution8(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;
//此上已经构造两个链表具有公共节点
stack<LNode*> S1; stack<LNode*> S2;
p=L1->next;q=L2->next;
while(p){
S1.push(p);
p=p->next;
}
while(q){
S2.push(q);
q=q->next;
}
while(S1.top()==S2.top()){
L3=S1.top();
S1.pop();
S2.pop();
}
return L3;
}
void Solution9(LNode* &L){
if(L->next==NULL){
return;
}
LNode* p=L;//p用来确定遍历多少次
cout<<"此时的从小到大的输出顺序是";
while(p->next!=NULL){
int min=L->next->data;
LNode* CurMin=L;
for(LNode* cur=L->next;cur->next!=NULL;cur=cur->next){
if(cur->next->data<min){
min=cur->next->data;
CurMin=cur;
}
}
LNode* OldCurMin=CurMin->next;
CurMin->next=CurMin->next->next;
free(OldCurMin);
cout<<min<<" ";
}
cout<<endl;
}
void Solution10(LNode* &L){
LNode* L2;LNode* OldL;
LNode* p=L->next;
queue<int> Q1;
queue<int> Q2;
while(p){
Q1.push(p->data);
p=p->next;
if(p){
Q2.push(p->data);
p=p->next;
}
}
p=L->next;
while(p){
while(!Q1.empty()){
p->data=Q1.front();
Q1.pop();
OldL=p;
p=p->next;
}
L2=p;
while(!Q2.empty()){
p->data=Q2.front();
Q2.pop();
p=p->next;
}
}
OldL->next=NULL;
cout<<"此时第一个链表是"<<endl;
PrintHead(L);
cout<<"此时第二个链表是"<<endl;
Print(L2);
}
void Insert(LNode* &L,LNode* &L2){//给定两个结点 将第二个结点插入到第一个结点之后
L2->next=L->next;
L->next=L2;
}
void Delete(LNode* &L){//给定一个结点删除它的后继结点
if(L->next==NULL){
return ;
}
L->next=L->next->next;
return ;
}
void Solution11(LNode* &L){
if(L->next==NULL){
cout<<"此时是空表"<<endl;
return;
}
LNode* p=L->next;//用于遍历链表
LNode* tail=L;
while(tail->next){//来找尾指针
tail=tail->next;
}
LNode* cur=L->next->next;//对链表的偶数项进行遍历
LNode* PreCur=L->next;//用于保存cur指针的前驱 防止断链
while(cur!=tail){
Delete(PreCur);
PreCur=cur->next;
Insert(tail,cur);
cur=PreCur->next;
}
PreCur->next=NULL;
Print(tail);
PrintHead(L);
}
void Solution12(LNode* &L){
if(L->next==NULL){
cout<<"此时链表是空"<<endl;
}
LNode* p=L->next;
LNode* q=L->next;
while(q){
if(q->data!=p->data){
p->next->data=q->data;
p=p->next;
}
q=q->next;
}
//释放p之后的空间
q=p->next;
while(q){
LNode* Oldq=q->next;
free(q);
q=Oldq;
}
p->next=NULL;
PrintHead(L);
}
LNode* Solution13(LNode* &L1,LNode* &L2){
LNode* p=L1;
LNode* q=L2;
LNode* Oldq;
while(q->next!=NULL&&p->next!=NULL){
if(q->next->data<=p->next->data){
//将q的后一个结点插入到p之后
Oldq=q->next;
q->next=q->next->next;
Oldq->next=p->next;
p->next=Oldq;
}
else{
p=p->next;
}
}
if(p->next==NULL){
p->next=q->next;
}
PrintHead(L1);
//接下来原地反转数组便可
if(L1->next->next==NULL){
return L1;
}
p=L1->next;
q=p->next;
LNode* r=q;
LNode* tail=p;
while(r){
r=q->next;
q->next=p;
p=q;
q=r;
}
L1->next=p;
tail->next=NULL;
PrintHead(L1);
}
void Solution14(LNode* &L1,LNode* &L2){
LNode* p=L1->next;LNode* q=L2->next;
LNode* L3=(LNode*)malloc(sizeof(LNode));//重新定义的一个新链表
LNode* tail=L3;//新链表的尾指针
while(p&&q){
if(p->data==q->data){
LNode* cur=(LNode*)malloc(sizeof(LNode));
cur->data=p->data;
cur->next=NULL;
tail->next=cur;
tail=tail->next;
p=p->next;
q=q->next;
}
else if(p->data<q->data){
p=p->next;
}
else{
q=q->next;
}
}
PrintHead(L3);
}
void Solution15(LNode* &L1,LNode* &L2){
LNode* p=L1->next;LNode* q=L2->next;
LNode* r=L1;
while(p&&q){
if(p->data==q->data){
r->next->data=p->data;
p=p->next;
q=q->next;
r=r->next;
}
else if(p->data<q->data){
p=p->next;
}
else{
q=q->next;
}
}
r->next=NULL;
PrintHead(L1);
}
void GetNext(vector<int> V,int next[]){
next[1]=0;//相当于一个标志位
int i=1;//i用来指向第二个字符
int j=0;//j的指向要比i小
while(i<V.size()){
if(j==0||V[i-1]==V[j-1]){
++i;++j;
next[i]=j;
}
else{
j=next[j];
}
}
}
int KMP(vector<int> V1,vector<int> V2,int next[]){
int i= 1, j= 1;
while (i<=V1.size()&&j<=V2.size()){//因为表示的是位置 所以认为需要比对到=
if (j == 0 || V1[i-1]== V2[j-1]){
++i; ++j;
}
else
j=next[j];
}
if (j >V2.size())//因为是位置 这里需要> 单纯的等于可能不行
return i - V2.size();
else
return 0;
}
void Solution16(LNode* L1,LNode* L2){
LNode* p=L1->next;
LNode* q=L2->next;
vector<int> V1;
vector<int> V2;
while(p){
V1.push_back(p->data);
p=p->next;
}
while(q){
V2.push_back(q->data);
q=q->next;
}
int next[V2.size()+1];
GetNext(V2,next);
if(KMP(V1,V2,next)>0){
cout<<"此时能匹配并且位置是"<<KMP(V1,V2,next)<<endl;
}
else{
cout<<"此时不能模式匹配"<<endl;
}
}
void Menu(){
int choice;
cout<<"请输入你要解决第几题"<<endl;
cin>>choice;
switch(choice){
case 8:{
LNode* L1;LNode* L2;LNode* L3;
L1=InitHeadList();
L2=InitHeadList();
L3=Solution8(L1,L2);
Print(L3);
break;
}
case 9:{
LNode* L;
L=InitHeadList();
Solution9(L);
PrintHead(L);
break;
}
case 10:{
LNode* L;
L=InitHeadList();
Solution10(L);
break;
}
case 11:{
LNode* L;
L=InitHeadList();
Solution11(L);
break;
}
case 12:{
LNode* L;
L=InitHeadList();
Solution12(L);
break;
}
case 13:{
LNode* L1;LNode* L2;
L1=InitHeadList();
L2=InitHeadList();
Solution13(L1,L2);
break;
}
case 14:{
LNode* L1;LNode* L2;
L1=InitHeadList();
L2=InitHeadList();
Solution14(L1,L2);
break;
}
case 15:{
LNode* L1;LNode* L2;
L1=InitHeadList();
L2=InitHeadList();
Solution15(L1,L2);
break;
}
case 16:{
LNode* L1;LNode* L2;
L1=InitHeadList();
L2=InitHeadList();
Solution16(L1,L2);
break;
}
}
}
int main(){
Menu();
}
感觉不错点个赞呗