共享
题目 共享
思路分析
目标
- 找到两个单词（用链表表示）共同后缀的起始位置。
关键点
- 链表长度可能不同： 两个单词的长度（即链表的长度）可能不一致。
- 共享后缀： 两个链表可能在某一点开始共享后缀。
- 独立部分和共享部分： 每个链表可以视为由独立部分（X或Y）和共享部分（Z）组成。
工作原理
- 遍历策略：
- 使用两个指针分别从两个链表的头节点开始遍历。
- 当任一指针到达链表末尾（节点为
-1），将其移至另一链表的头节点继续遍历。
- 同步相遇：
- 由于遍历策略，两个指针将遍历等长的路径：
X + Z + Y和Y + Z + X。 - 如果有共享后缀（Z部分），两指针会在Z的起始位置相遇。
- 如果没有共享后缀，两指针会在遍历完各自链表后同时到达
-1。
- 输出结果：
- 如果两个指针相遇，则输出相遇节点的地址（共享后缀的起始位置）。
- 如果两个指针同时到达
-1，输出-1，表示没有共享后缀。
优势
- 无需知道链表长度： 算法不需要预先计算链表的长度。
- 无需修改链表： 直接在原链表上操作，不需要任何结构修改。
- 高效实用： 通过一个简单的遍历策略高效地找到可能的共享部分。
即第一个链表为x+z 第二个为y+z 若一个先走完再走另一个 则一定会有x+z+y=y+z+x 所以能找到z的起始位置 然后如果z不存在 x+y也一定会等于y+x 即同时到-1位置
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int ne[N];//用不到数据域
int head1,head2;
int n;
int main()
{
cin>>head1>>head2>>n;
for(int i=0;i<n;i++){
int addr,nextaddr;
char data;
cin>>addr>>data>>nextaddr;
ne[addr]=nextaddr;
}
int i=head1,j=head2;
if(i!=-1 && j!=-1){
while(i!=j){
if(i==-1)
i=head2;
if(j==-1)
j=head1;
i=ne[i];
j=ne[j];
}
}
if(i==-1 || j==-1)
cout<<"-1"<<endl;
else
printf("%05d\n",i);
// cout << setfill('0') << setw(5) << i << endl;
return 0;
}
💬 评论