共享

题目 共享

image-00e72663

思路分析

目标

  • 找到两个单词（用链表表示）共同后缀的起始位置。

关键点

  • 链表长度可能不同： 两个单词的长度（即链表的长度）可能不一致。
  • 共享后缀： 两个链表可能在某一点开始共享后缀。
  • 独立部分和共享部分： 每个链表可以视为由独立部分（X或Y）和共享部分（Z）组成。

工作原理

  1. 遍历策略：
  • 使用两个指针分别从两个链表的头节点开始遍历。
  • 当任一指针到达链表末尾（节点为-1），将其移至另一链表的头节点继续遍历。
  1. 同步相遇：
  • 由于遍历策略，两个指针将遍历等长的路径：X + Z + Y 和 Y + Z + X。
  • 如果有共享后缀（Z部分），两指针会在Z的起始位置相遇。
  • 如果没有共享后缀，两指针会在遍历完各自链表后同时到达-1。
  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;

}

同类题型

视频讲解

⬅️ 调整数组顺序使奇数位于偶数前面 🏠 00-刷题理模型 ➡️ 寻找重复数