【解法4】链表操作，前后指针
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法4】链表操作，前后指针
(1)初始时设置两个指针left和right都指向头结点，right指针先后移k次，若此过程中left指向了NULL则查找失败，返回0。然后将left和right同时后移，直到right指向NULL为止，因为left和right直接相差k次移动，所以此时left一定指向倒数第k个结点，输出left，返回1。（2）算法V如下：
<!-- verified-by-hand -->
> [!success] 已结合原文第 138 页及 Markdown 上下文人工校对
> 形参间逗号丢失，函数末尾花括号和孤立字符丢失。
int ans(node *list, int k)
{
node *left = list, *right = list;
for (int i = 0; i < k; i++)
{
right = right->link;
if (right == NULL) return 0;
}
while (right != NULL)
{
left = left->link;
right = right->link;
}
printf("%d\n", left->data);
return 1;
}
原资料配图 · 转写内容请回源核验
和str2分别指向两个单词所在单链表的头结点，链表结点结构为：
设str1
<!-- page 139 -->
<table><tr><td>data next</td></tr></table>
请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求：1)给出算法的基本设计思想。2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。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(n2)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>11</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>链表转数组</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>13</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>多指针法</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>15</td></tr></table>
请注意本题是返回地址，而对于相同后缀来说，只要发现两个链指向了同一个结点，后面的部分也会相同。即地址相同等价于后缀完全相同。 ”
## 【解法1】暴力解：枚举str1和str2起始位置
(1)设str1和str2的长度较大的值是n，两层for循环枚举str1和str2相同后缀的起始位置。
(2) 算法如下：
Node* ans(Node *str1, Node *str2)
{
Node* p1=str1->next; // str1的后缀起始位置
Node* p2; //之后循环中会赋初值
while (p1!=NULL)
{
p2=str2->next;
while (p2!=NULL)
if (p1==p2)
return p1; //后缀完全匹配，返回p1
p2=p2->next;
p1=p1->next;
}
return NULL;
}
Node* ans(Node *str1, Node *str2)
{
Node*S1[maxn],S2[maxn]; //保存str1和str2各结点地址，maxn是最大可能长度
Node* p1=str1->next; //_str1的后缀起始位置
Node* p2=str2->next;
int Len1=0, Len2=0;
while (p1!=NULL)
S1[Len1]=p1;
Len1++;
p1=p1->next;
while (p2!=NULL) // 草机考研
{
S2[Len2]=p2;
Len2++;
p2=p2->next;
if (S1[Len1-1]!=S2[Len2-1])
return NULL; //无相同后缀，可不写
for (int i=1; i<=min(Len1,Len2); i++) // 讨论相同后缀长度
if (S1[Len1-i]!=S2[Len2-i])
return S1[Len1-i+1];
return S1[0]; // 若S1和S2相同则返回首个字母地址
}
}
Node* ans(Node *str1, Node *str2)
{
Node* p1=str1->next; //指针p1用来遍历str1
Node* p2=str2->next; //指针p2用来遍历str2
int Len1=0, Len2=0;
while (p1!=NULL)
{
Len1++;
p1=p1->next;
while (p2!=NULL)
{
Len2++;
p2=p2->next;
}
p1=str1->next;
p2=str2->next;
if (Len1>Len2)
p1=p1->next;
else
for (int i=0; i<Len2-Len1; i++) // str2更长，p2先移动—段
p2=p2->next;
while (p1!=NULL && p2!=NULL)
{
if (p1==p2) return p1;
p1=p1->next;
p2=p2->next;
}
return NULL; //无相同后缀，可不写
}
}
原资料配图 · 转写内容请回源核验
(1)给出算法的基本设计思想。(2)使用C 或C++语言，给出单链表结点的数据类型定义。(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。(4)说明你所设计算法的时间复杂度和空间复杂度。 道
<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(m2)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>11</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>散列表</td><td rowspan=1 colspan=1>O(m)</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>15</td></tr></table>
【解法1】暴力解：枚举，每一个结点都和其他结点比较
<!-- page 142 -->
(1)两层循环枚举所有结点的两两比较，外层遍历链表中的结点p，内层q遍历p之后的结点，将和p绝对值相等的结点删除（只保留第一个出现的p）。
## (2) 结点数据结构定义：
typedef struct Node{
int data; // 该结点权值
struct Node *link; // 下—个结点
}Node;
void ans(Node* HEAD)
{
// 外层遍历结点p
Node *pre, *r; // pre是q前一个结点
//外层循环固定p，pre从p的下一个结点开始，遍历对比p的数据
while (p!=NULL)
{
pre=p; //每次都需要更新pre,从p开始
while (pre->link!=NULL)
{
q=pre->link; // q表示待比较结点
if (abs(p->data)==abs(q->data))
{
pre->link=q->link;
free(q);
}
else
pre=pre->link;
}
p=p->link;
}
}
typedef struct Node{
int data; // 该结点权值
struct Node *link; // 下—个结点
}Node;
void ans(Node* HEAD, int m, int n)
{
Node* p=HEAD->link; // 当前访问结点p
Node* pre=HEAD;
int count[n+1]={0};
while (p!=NULL)
{
if (count[abs(p->data)]==0)
{
count[abs(p->data)]=1; // p的权值第一次出现
pre=p;
p=p->next;
}
else
{ //p的权值前面已经出现过，删除p结点
pre->link=p->link;
free(p);
p=pre->link;
}
}
}
typedef struct node {
int data;
struct node* next;
} NODE;
void ans(Node* L)
{
// 统计链表结点数
Node *p = L->next;
int n = 0;
while (p != NULL)
{
n++;
}
//链表分成两半，p指向后一半第一个结点
p = L;
for (int i=0; i<(n+1)/2; i++)
p = p->next;
Node *temp = p;
p = p->next;
temp->next = NULL;
//将后一半结点依次插入到前一半
for (int i=0; i<n/2; i++)
{
temp = p->next;
Node *pre = L;
for (int j=0; j<n/2-i; j++)
pre = pre->next;
p->next = pre->next;
pre->next = p;
p = temp; // 更新下一个待处理元素 p
}
}
//头插法
void Head_Insert(Node* L, Node* p)
{
p->next=L->next;
L->next=p;
}
void ans(Node* L)
{
// 找中间结点 p
Node *p, *q;
p = q = L->next;
while (p != NULL && q != NULL)
{
q = q->next;
if (q == NULL I1 q->next == NULL)
break;
q = q->next;
p = p->next;
}
// 链表从 p 后分成两半
Node *temp = p;
p = p->next;
temp->next = NULL;
//为链表后一半设置新的头结点
Node *L2 = (Node*)malloc(sizeof(Node))
L2->next = NULL;
//将后一半结点逆置
while (p != NULL)
{
temp = p->next;
Head_Insert(L2, p);
p = temp;
Node *p2 = L2->next;
// 将前一半链表和逆置后的后一半链表交叉合并
while (p2 != NULL)
暂存 p1 和 p2 的下一个结点
Node* temp1 = p1->next;
Node* temp2 = p2->next;
// p2 插入到 p1 后面
p2->next = p1->next;
p1->next = p2;
// 更新 p1 和 p2
p1 = temp1;
p2 = temp2;
}
}