力扣每日一题——找到离给定两个节点最近的节点
目录
题目链接：2359. 找到离给定两个节点最近的节点 - 力扣（LeetCode）
题目描述
解法一：双指针路径交汇法
基本思路
关键步骤
为什么这样可行呢我请问了？
举个例子
特殊情况
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
总结
题目链接：2359. 找到离给定两个节点最近的节点 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。
有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。
同时给你两个节点 node1 和 node2 。
请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。
注意 edges 可能包含环。
示例 1：
输入：edges = [2,2,3,-1], node1 = 0, node2 = 1 输出：2 解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。 两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。
示例 2：
输入：edges = [1,2,-1], node1 = 0, node2 = 2 输出：2 解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。 两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。
提示：
n == edges.length2 <= n <= 105-1 <= edges[i] < nedges[i] != i0 <= node1, node2 < n
解法一：双指针路径交汇法
这道题目的核心是在一个有向图中，每个节点最多只有一条出边，可能存在环。给定两个起点 node1 和 node2，要找一个节点 x，使得两个起点都能到达 x，并且两个起点到 x 的距离中较大的那个值尽可能小。如果多个节点满足条件，选编号最小的；如果不存在，返回 -1。
基本思路
因为每个节点最多只有一条出边，整个图的结构其实很简单：从任意节点出发，沿着出边走，要么走到尽头（遇到 -1），要么进入一个环然后开始循环。这种结构决定了从 node1 或 node2 出发的路径是唯一的，不会分叉，只是可能绕圈。
关键步骤
-
分别计算两个起点能到达哪些节点
用两个数组（比如dist1和dist2）记录 node1 和 node2 到每个节点的距离。初始化时都设为 -1，表示不可达。然后从 node1 出发，沿着出边走，每走一步记录当前步数（距离），直到走到尽头或遇到已经访问过的节点（说明进入环了，再走会重复，此时停掉）。对 node2 同样操作一遍。 -
处理环的干扰
如果路径进入环，比如从 node1 走到节点 A 后开始绕圈，那么第一次走到 A 时的距离就是最短距离。之后再绕圈只会让距离变大，所以遇到访问过的节点直接停掉，避免死循环。 -
找最优节点
遍历所有节点，如果一个节点在dist1和dist2中都有记录（说明两个起点都能到达它），就计算max(dist1[i], dist2[i])（即两个距离的较大值）。我们需要的正是这个较大值最小的节点。如果有多个节点值相同，选编号最小的那个。
为什么这样可行呢我请问了？
- 路径唯一性：因为每个节点最多一条出边，从起点出发的路径是唯一的，不会分叉，所以记录的距离就是最短距离。
- 环的处理：遇到环就停，保证了第一次到达节点的距离是最小的，后续绕圈只会增加距离，不用考虑。
- 最优解筛选：直接比较所有公共节点的距离较大值，取最小值，符合题目要求。
举个例子
假设图是 edges = [2, 2, 3, -1]，node1=0，node2=1：
- node1（0）的路径：0 → 2 → 3，距离
dist1[2]=1，dist1[3]=2。 - node2（1）的路径：1 → 2 → 3，距离
dist2[2]=1，dist2[3]=2。
公共节点是 2 和 3。节点 2 的较大值是max(1,1)=1，节点 3 是max(2,2)=2，所以选节点 2。
特殊情况
如果两个起点没有公共可达节点（比如一个走到尽头，另一个进环但路径不重合），直接返回 -1。
Java写法：
class Solution {public int closestMeetingNode(int[] edges, int node1, int node2) {int n = edges.length;int[] dist1 = new int[n];int[] dist2 = new int[n];Arrays.fill(dist1, -1);Arrays.fill(dist2, -1);// 计算 node1 到各节点的距离int cur = node1, steps = 0;while (cur != -1 && dist1[cur] == -1) {dist1[cur] = steps++;cur = edges[cur];}// 计算 node2 到各节点的距离cur = node2;steps = 0;while (cur != -1 && dist2[cur] == -1) {dist2[cur] = steps++;cur = edges[cur];}// 寻找最优节点int minMaxDist = Integer.MAX_VALUE;int ans = -1;for (int i = 0; i < n; i++) {if (dist1[i] != -1 && dist2[i] != -1) {int maxDist = Math.max(dist1[i], dist2[i]);if (maxDist < minMaxDist || (maxDist == minMaxDist && i < ans)) {minMaxDist = maxDist;ans = i;}}}return ans;}
}C++写法：
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;class Solution {
public:int closestMeetingNode(vector<int>& edges, int node1, int node2) {int n = edges.size();vector<int> dist1(n, -1);vector<int> dist2(n, -1);// 计算 node1 到各节点的距离int cur = node1, steps = 0;while (cur != -1 && dist1[cur] == -1) {dist1[cur] = steps++;cur = edges[cur];}// 计算 node2 到各节点的距离cur = node2;steps = 0;while (cur != -1 && dist2[cur] == -1) {dist2[cur] = steps++;cur = edges[cur];}// 寻找最优节点int minMaxDist = INT_MAX;int ans = -1;for (int i = 0; i < n; i++) {if (dist1[i] != -1 && dist2[i] != -1) {int maxDist = max(dist1[i], dist2[i]);if (maxDist < minMaxDist || (maxDist == minMaxDist && i < ans)) {minMaxDist = maxDist;ans = i;}}}return ans;}
};运行时间
时间复杂度和空间复杂度
时间复杂度：O(n)
空间复杂度：O(n)
总结
问题核心：给定一个有向图（节点最多一条出边，可能存在环），需找到节点 node1 和 node2 均可达的节点，使两者到该节点距离的较大值最小化。若有多个解，返回最小节点编号；无解则返回 -1。
解法精髓：采用 双指针路径交汇法（Dual-Pointer Path Convergence）