【解法2】多指针法+逆置
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法2】多指针法+逆置
(1)①使用快慢指针找到链表的中点(slow指向后半段的前一个位置)。②翻转链表的后半段。③同时遍历前半段和翻转后的后半段，逐个比较结点的值。④如果所有结点的值都相等，则链表是对称的，返回1；否则，链表不是对称的，返回0。(2)代码如下：
//头插法:将p插入到以L 为头结点的链表开头
linklist Head_Insert(linklist L, linklist p)
{
ListNode* temp=p->next;
L->next=p;
return temp;
}
int IsPalindrome(linklist L)
{
if (L==NULL L->next==NULL) //链表为空或一个结点时
return 1;
linklist fast=L->next, slow=L->next;
//使用快慢指针找到中点 slow,使得slow->next 是后半段起点
while (fast->next!=NULL && fast->next->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
linklist p2=slow->next; //后半段从slow->next开始
linklist p1=L->next; //前半段从开始，到slow结束
slow->next=NULL;
//翻转链表的后半段
linklist L2=(linklist)malloc(sizeof(node)); // 后半段链表头
L2->next=NULL;
while (p2!=NULL)
p2=Head_Insert(L2,p2);
p2=L2->next; // p2指向L2的第一个元素
//比较前半段和翻转后的后半段的结点值
while (p1!=NULL && p2!=NULL)
if(p1->data!=p2->data)
return 0;
p1=p1->next;
p2=p2->next;
return 1;
}
}
原资料配图 · 转写内容请回源核验
类型定义(2)采用C或C++语言描述算法，关键之处给出注释。
间复杂度。
(1) 写出链表结点的数据
(3) 说明所设计算法的时
<table><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>做题思路</td><td rowspan=1 colspan=1>时间复杂度</td><td rowspan=1 colspan=1>空间复杂度</td><td rowspan=1 colspan=1>预计得分</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>枚举法</td><td rowspan=1 colspan=1>O(mn)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>9</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>多指针法</td><td rowspan=1 colspan=1>O(m + n)</td><td rowspan=1 colspan=1>O(1)</td><td rowspan=1 colspan=1>13</td></tr></table>
## 【解法1】枚举法
对 L2 的每一项从头遍历，尝试将其插入到 L1 中合适的位置；
(1) 定义：
typedef struct Node{
int data;
int exp;
struct Node *next;
}Node, *LinkList;
void Find_Insert(LinkList pre, LinkList p) // 查找并插入p
{
while (pre->next!=NULL && pre->next->exp>p->exp) // 查找插入位置
pre=pre->next;
Linklist temp=pre->next;
//将p插入到pre后面
if (temp==NULL || temp->exp<p->exp)
{
p->next=temp;
pre->next=p;
return;
}
//次数相等，合并同类型
temp->data+=p->data;
if (temp->data==0) //如果相加后系数=0则删除
pre->next=temp->next;
}
LinkList ans(LinkList L1, LinkList L2)
{
LinkList_p=L2->next; // p2遍历链表L2
while(p!=NULL)
{
LinkList temp=p->next;
Find_Insert(L1, p);
p=temp;
} return L1;
}
typedef struct Node{
int data;
int exp;
struct Node *next;
}Node, *LinkList;
void Insert(Linklist pre, LinkList p)
{
p->next=pre->next; pre->next=p;
}
LinkList ans(LinkList L1, LinkList L2)
{
LinkList p1=L1->next; // p1遍历L1表
LinkList p2=L2->next; //p2遍历L2表
LinkList pre1=L1; // pre1是p1前一个结点
while (p1!=NULL && p2!=NULL)
{
// p1的指数更高则继续遍历L1
{
pre1=p1;
p1=p1->next;
}
else if(p1->exp<p2->exp) // p1的指数更低则将p2插入pre1后
Linklist temp=p2->next;
Insert(pre1,p2);
pre1=p2;
} p2=temp;
else //p1、p2指数相同则相加并判断是否删除
{
p1->data+=p2->data;
if (p1->data==0) // 若为0则删除p1结点
pre1->next=p1->next;
else
pre1=p1; // 若不为0则更新pre1
p1 = p1->next;
p2 = p2->next;
}
}
if (p2!=NULL)
//如果链表L2还未访问完则接到pre1后面
return L1;
} HN
typedef struct node{
int data;
struct node *next;
}node, *LinkList;
LinkList ans(LinkList L1, LinkList L2)
{
LinkList p1=L1->next; // p1遍历L1表
LinkList pre1=L1;
while (p1!=NULL)
{
LinkList p2=L2->next; // p2遍历L2表
while(p2!=NULL)
{
if (p1->data==p2->data) break;
p2=p2->next;
}
if(p2==NULL)
pre1->next=p1->next; //没出现过则删除结点p1,pre1不需要更新
else
pre1=pre1->next; //出现过则不删除结点p1,pre1后移
p1=p1->next;
}
return L1;
}
LinkList ans(LinkList L1, LinkList L2)
{
LinkList p1=L1->next; // p1遍历L1表
LinkList p2=L2->next; //p2遍历L2表
LinkList pre1=L1; //pre1是p1前一个结点
while (p1!=NULL && p2!=NULL)
{
if (p1->data<p2->data) //p1->data小则删除p1结点，p1前移继续寻找
{
pre1->next=p1->next;
p1=p1->next;
}X
else if(p1->data>p2->data) // p2->data 小,p2前移继续寻找
p2=p2->next;
else
//p1、p2的data相同则保留p1结点，p1、p2都前移继续寻找
{
pre1=p1; // 更新pre1
p1=p1->next; p2=p2->next; // 首
}
while (p1 != NULL)
{ //如果链表L1还有剩余元素也删去他们
pre1->next = p1->next;
p1 = pre1->next;
return L1;
}
}
}
int ans(node* list, int k)
{
node* p;
node* q=NULL; // q=NULL是倒数第0个结点
for (int i=1; i<=k; i++)
{
p=list->link;
if (q==p) return 0; //找不到倒数第k个结点
while (p->link!=q)
p=p->link; // p最终是倒数第i个结点
q=p;
}
printf("%d\n", p->data); // 输出倒数第k个结点的值
return 1;
}
int ans(node* list, int k)
{
node* A[maxn]; //结点数组
node* p=list->link; //正在遍历的结点
int n=0; //数组中结点个数
{
A[n++]=p;
p=p->link;
}
if (n<k) return 0;
printf("%d\n",A[n-k]->data);// 输出倒数第k个元素的值
return 1;
}
int ans(node* list, int k)
{
node* p=list->link;
int t, n=0;
while (p!=NULL)
n++;
p=p->link;
}
t=n-k+1;
if (t<=0) return 0;
p=list; // 从头结点开始往后移t次
for (int i=0; i<t; i++)
p=p->link;
printf("%d\n", p->data); // 输出倒数第k个元素的值