1.题目： ?判断一个链表是否为回文结构
描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 0 \le n \le 10^50≤n≤10?
?链表中每个节点的值满足 |val| \le 10^7∣val∣≤10?
2.算法：
//1.暴力算法：全部反转 ?
//2.双指针算法 半边链表反转?
算法思想：
1.暴力算法：新建一个相同的链表? 反转他? 比较值的大小
2.双指针算法 半边链表反转 ：
- 空间复杂度：O(n)O(n)O(n)，记录链表元素的辅助数组
知识点：双指针
双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。
思路：
在数组中，我们可以借助双指针，一个从前往遍历前一半数组，另一个从后往前遍历后一半数组，依次比较值。链表中如果我们要用这样的思想，左指针从前往后很容易，直接的链表的遍历就可以了。但是右指针是真的没有办法从尾巴往前走，要是链表后半段的指针是逆序的就好了。
怎么样能让链表后半段的指针反过来，将后半段链表整体反转不就行了吗？如果我们将后半段链表整体反转，那么相当于后半段就是从末尾指向中间，就可以实现后半段的逆序遍历——按照指针直接走就可以了。
具体做法：
- step 1：遍历链表，统计链表的长度。
- step 2：将长度除2，遍历这么多位置，找到链表的中点。
- step 3：从中点位置开始，对链表后半段进行反转。
- step 4：与方法二类似，双指针左指针指向链表开头，右指针指向链表尾，此时链表前半段是正常的，我们也可以正常遍历，但是链表后半段所有指针都被我们反转逆序，因此我们可以从尾节点往前遍历。
- step 5：依次比较对应位置的元素值是否相等。
3.双指针找中点（推荐使用）
思路：
上述方法三找中点，我们遍历整个链表找到长度，又遍历长度一半找中点位置。过程过于繁琐，我们想想能不能优化一下，一次性找到中点。
我们首先来看看中点的特征，一个链表的中点，距离链表开头是一半的长度，距离链表结尾也是一半的长度，那如果从链表首遍历到链表中点位置，另一个每次遍历两个节点的指针是不是就到了链表尾，那这时候我们的快慢双指针就登场了：
具体做法：
- step 1：慢指针每次走一个节点，快指针每次走两个节点，快指针到达链表尾的时候，慢指针刚好到了链表中点。
- step 2：从中点的位置，开始往后将后半段链表反转。
- step 3：按照方法三的思路，左右双指针，左指针从链表头往后遍历，右指针从链表尾往反转后的前遍历，依次比较遇到的值
4.代码：
/*************************************************
作者：She001
时间:2022/9/30
题目： 判断一个链表是否为回文结构
描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 0 \le n \le 10^50≤n≤10
链表中每个节点的值满足 |val| \le 10^7∣val∣≤10
***************************************************/
//算法：
//1.暴力算法：全部反转
//2.双指针算法 半边链表反转
#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
int i;
node *next;
};
void print(node * head)//打印链表
{
node* pp= head;//复制头节点
while(pp!=NULL)//判断这个节点是否为空 链表是否结束
{
cout<<pp->i<<" ";
pp=pp->next;//指向下一个
}
cout<<endl;
}
int lianbiao_num(node * head)//函数的作用 返回链表的个数
{
int i=0;
node* pp=head;
while(pp!=NULL)
{
i++;
pp=pp->next;
}
//cout<<"链表中节点的个数: "<<i<<endl;
return i;
}
node * reverseList(node* head)//翻转链表
{
if(head==NULL)
{
return NULL;
}
node * a = head;
node * b = NULL;
while(a!=NULL)
{
node * c = a->next;
a->next=b;
b=a;
a=c;
}
return b;
}
//1.暴力算法：全部反转
//
bool fangfa_1(node * head)
{
if(head==NULL)//链表为空返回 是回文
{
return true;
}
if(lianbiao_num(head)==1)//链表只有一个 返回是回文
{
return true;
}
node* a1=head;//指针遍历 链表
node* head2=new node;//建立的另外节点的头节点
node* hh=head2;//第二个节点的指针 方便连接
while(a1!=NULL)//建立第二个链表
{
hh->i=a1->i;//第二个链表赋值
a1=a1->next;//指向下一个节点
if(a1==NULL)//判断下一个 节点是否空
{
hh->next=NULL;
}
else
{
hh->next = new node;
hh=hh->next;
}
}
node * h1= reverseList(head2);//翻转第二个链表
hh=h1;
a1=head;
while(hh!=NULL && a1!=NULL)
{
if((hh->i) != (a1->i))
{
while(h1!=NULL)//销毁建立的链表
{
node * p=h1;
h1=h1->next;
delete p;
}
return false;
}
hh=hh->next;
a1=a1->next;
}
while(h1!=NULL)//销毁建立的链表
{
node * p=h1;
h1=h1->next;
delete p;
}
return true;
}
//2.双指针算法 半边链表反转
bool fangfa_2(node* head)
{
if(head==NULL)//链表为空返回 是回文
{
return true;
}
if(lianbiao_num(head)==1)//链表只有一个 返回是回文
{
return true;
}
node * a1=head;
node * a2=head;
//双指针寻找中点
while(a2!=NULL && a2->next!=NULL)//这里考虑了 单数的情况 所以 123454321 会 a1 -> 5 |||| 12345 54321 a1-> 第二个 5
{
a1=a1->next;
a2=a2->next->next;
}
a1=reverseList(a1);//翻转中间到后面的代码
a2=head;//等于头部代码
//链表的情况
// 1 -> 2-> 3-> 4-> 5 <-4 <-3<- 2 <-1
// 1-> 2 -> 3 -> 4 -> 5 ->5 <- 4<- 3 <- 2 <-1
while(a1!=NULL)//判断是否回文
{
if((a1->i)!=(a2->i))
{
return false;
}
a1=a1->next;
a2=a2->next;
}
return true;
}
int main()
{
//建立 第一个 单链表
node *a1=new node;
node *a2=new node;
node *a3=new node;
node *a4=new node;
node *a5=new node;
node *a6=new node;
node *a7=new node;
node *a8=new node;
node *a9=new node;
a1->i=2;//链表节点的复制
a2->i=1;
a3->i=4;
a4->i=3;
a5->i=7;
a6->i=8;
a7->i=9;
a8->i=6;
a9->i=5;
a1->next=a2;//链表的连接
a2->next=a3;
a3->next=a4;
a4->next=a5;
a5->next=a6;
a6->next=a7;
a7->next=a8;
a8->next=a9;//a5 是 两个链表的节点
a9->next=NULL;
//建立 第二个 单链表
node *b1=new node;
node *b2=new node;
node *b3=new node;
node *b4=new node;
node *b5=new node;
node *b6=new node;
node *b7=new node;
node *b8=new node;
node *b9=new node;
b1->i=1;//链表节点的复制
b2->i=2;
b3->i=3;
b4->i=4;
b5->i=5;
b6->i=4;
b7->i=3;
b8->i=2;
b9->i=1;
b1->next=b2;//链表的连接
b2->next=b3;
b3->next=b4;
b4->next=b5;
b5->next=b6;
b6->next=b7;
b7->next=b8;
b8->next=b9;//a5 是 两个链表的节点
b9->next=NULL;
/*
int a=fangfa_1(a1);
if(a==1)
{
print(a1);
cout<<"这个链表是回文！"<<endl;
}
else
{
print(a1);
cout<<"这个链表不是回文!"<<endl;
}
int b=fangfa_1(b1);
if(b==1)
{
print(b1);
cout<<"这个链表是回文！"<<endl;
}
else
{
print(b1);
cout<<"这个链表不是回文!"<<endl;
}
*/
int a=fangfa_2(a1);
if(a==1)
{
print(a1);
cout<<"这个链表是回文！"<<endl;
}
else
{
print(a1);
cout<<"这个链表不是回文!"<<endl;
}
int b=fangfa_2(b1);
if(b==1)
{
print(b1);
cout<<"这个链表是回文！"<<endl;
}
else
{
print(b1);
cout<<"这个链表不是回文!"<<endl;
}
return 0;
}