---
title: "共享"
created: 2025-11-28
tags:
  - 算法
---

# 共享

## 题目 [共享](https://www.acwing.com/problem/content/description/1518/)

![[image-00e72663.png]]

## 思路分析

### 目标

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

### 关键点

- **链表长度可能不同：** 两个单词的长度（即链表的长度）可能不一致。
- **共享后缀：** 两个链表可能在某一点开始共享后缀。
- **独立部分和共享部分：** 每个链表可以视为由独立部分（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位置

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[list|list]] 🏠 [[00-刷题理模型]] ➡️ [[区块反转|区块反转]]