目錄

題目鏈接：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.length
• 2 <= n <= 105
• -1 <= edges[i] < n
• edges[i] != i
• 0 <= node1, node2 < n

---

解法一：雙指針路徑交匯法?

????????這道題目的核心是在一個有向圖中，每個節點最多只有一條出邊，可能存在環。給定兩個起點 node1 和 node2，要找一個節點 x，使得兩個起點都能到達 x，并且兩個起點到 x 的距離中較大的那個值盡可能小。如果多個節點滿足條件，選編號最小的；如果不存在，返回 -1。

基本思路

????????因為每個節點最多只有一條出邊，整個圖的結構其實很簡單：從任意節點出發，沿著出邊走，要么走到盡頭（遇到 -1），要么進入一個環然后開始循環。這種結構決定了從 node1 或 node2 出發的路徑是唯一的，不會分叉，只是可能繞圈。

關鍵步驟

1. ??分別計算兩個起點能到達哪些節點??
   用兩個數組（比如?dist1?和?dist2）記錄 node1 和 node2 到每個節點的距離。初始化時都設為 -1，表示不可達。然后從 node1 出發，沿著出邊走，每走一步記錄當前步數（距離），直到走到盡頭或遇到已經訪問過的節點（說明進入環了，再走會重復，此時停掉）。對 node2 同樣操作一遍。

2. ??處理環的干擾??
   如果路徑進入環，比如從 node1 走到節點 A 后開始繞圈，那么第一次走到 A 時的距離就是最短距離。之后再繞圈只會讓距離變大，所以遇到訪問過的節點直接停掉，避免死循環。

3. ??找最優節點??
   遍歷所有節點，如果一個節點在?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）