【解法2】多指针法+逆置
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法2】多指针法+逆置
(1）①使用快慢指针找到链表的中点（slow指向后半段的前一个位置）。②翻转链表的后半段。③同时遍历前半段和翻转后的后半段，逐个比较结点的值。④如果所有结点的值都相等，则链表是对称的，返回1；否则，链表不是对称的，返回0。
(2) 代码如下：
<!-- verified-by-hand -->
> [!success] 已结合原文第 91 页及 Markdown 上下文人工校对
> 按本页四步算法说明校正：保留快慢指针、切断与后半段逆置，将 return 1 移到完成全部比较之后
ListNode* Head_Insert(ListNode *L, ListNode *p)
{
ListNode *next = p->next;
p->next = L->next;
L->next = p;
return next;
}
int IsPalindrome(linklist L)
{
if (L == NULL || L->next == NULL) return 1;
linklist fast = L->next, slow = L->next;
while (fast->next != NULL && fast->next->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
linklist p1 = L->next;
linklist p2 = slow->next;
slow->next = NULL;
linklist L2 = (linklist)malloc(sizeof(node));
L2->next = NULL;
while (p2 != NULL)
p2 = Head_Insert(L2, p2);
p2 = L2->next;
while (p1 != NULL && p2 != NULL)
{
if (p1->data != p2->data) return 0;
p1 = p1->next;
p2 = p2->next;
}
return 1;
}
原资料配图 · 转写内容请回源核验
原资料配图 · 转写内容请回源核验
结果2X³-X²+3
原资料配图 · 转写内容请回源核验
(1) 写出链表结点的数据类型定义
(2)采用C或C++语言描述算法，关键之处给出注释。
(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; // temp是pre后一个位置
//将p插入到pre后面
if (temp==NULL || temp->exp<p->exp)
{
p->next=temp;
pre->next=p;
return;
}
//次数相等，合并同类型
temp->data+=p->data;
if (temp->data==0)
} pre->next=temp->next;
LinkList ans(LinkList L1, LinkList L2)
{
LinkList p=L2->next;
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;
LinkList p2=L2->next;
LinkList pre1=L1;
while (p1!=NULL && p2!=NULL)
{
if (p1->exp>p2->exp)
{
pre1=p1;
p1=p1->next;
}
else if (p1->exp<p2->exp)
{
Linklist temp=p2->next;
Insert(pre1,p2);
pre1=p2;
p2=temp;
}
else
{
p1->data+=p2->data;
if (p1->data==0)
pre1->next=p1->next;
else
pre1=p1;
p1 = p1->next;
p2 = p2->next;
}
}
if (p2!=NULL)
pre1->next=p2;
return L1;
}
}
// p1遍历L1表
// p2遍历L2表
// pre1是p1前一个结点
// p1的指数更高则继续遍历L1
// p1的指数更低则将p2插入pre1后
// p1、p2指数相同则相加并判断是否删除
//若为0则删除p1结点
//若不为0则更新pre1
//如果链表L2还未访问完则接到pre1后面
typedef struct node{
int data;
struct node *next;
}node, *LinkList;
LinkList ans(LinkList L1, LinkList L2)
{
LinkList p1 = L1->next;
LinkList pre1 = L1;
while (p1 != NULL)
{
LinkList p2 = L2->next;
while (p2 != NULL && p1->data != p2->data)
p2 = p2->next;
if (p2 == NULL) pre1->next = p1->next;
else pre1 = p1;
p1 = p1->next;
}
return L1;
}
原资料配图 · 转写内容请回源核验
## 【解法2】多指针法
(1)指针p1、p2分别遍历链表L1和L2，pre保存p1前一个结点，每次比较p1和p2:①如果p1->data ==p2->data，说明找到了相同的结点，保留p1结点，然后p1、p2同时后移；②如果p1->data>p2->data，说明p2->data在p1中不会出现，并将p2后移；③如果p1->data<p2->data，说明p1->data在p2中不会出现，删除p1结点，并将p1后移。继续按照上述步骤遍历，直到遍历完一个链表。如果链表L1还未遍历完，则剩下的元素也不需要，删除p1及之后的元素，最后返回L1。1 a
(2) 代码如下：
LinkList ans(LinkList L1, LinkList L2)
{
LinkList p1=L1->next;
}
LinkList ans(LinkList L1, LinkList L2)
{
LinkList p1 = L1->next, p2 = L2->next, pre1 = L1;
while (p1 != NULL && p2 != NULL)
{
if (p1->data < p2->data)
{
pre1->next = p1->next;
p1 = p1->next;
}
else if (p1->data > p2->data)
{
p2 = p2->next;
}
else
{
pre1 = p1;
p1 = p1->next;
p2 = p2->next;
}
}
pre1->next = NULL;
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;
}
(3) // 时间复杂度：O(n²) 空间复杂度：O(1)
int ans(node* list, int k)
{
node* A[maxn];
node* p=list->link;
int n=0;
while (p!=NULL)
{
A[n++]=p;
p=p->link;
}
if (n<k) return 0;
printf("%d\n", A[n-k]->data);
return 1;
}
//结点数组
// 正在遍历的结点
//数组中结点个数
//输出倒数第k个元素的值
int ans(node* list, int k)
{
node* p=list->link;
int t, n=0;
{
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个元素的值
return 1;
}