297. Where Two Chains Meet
Two delivery routes are stored as chains of stops. They start in different districts, but from some stop onward they may share the very same stops, because both routes use one shared stretch of road. Once two routes share a stop they share everything after it, and neither route has a loop.
Given the heads a and b of the two chains, return the first shared stop (the node object that is in both chains), or null if the routes never meet. In the test data the second chain is described by its own leading values plus joinParam and joinIndex, meaning that after those values it continues with node number joinIndex (0-based) of chain joinParam. Chains must be left unchanged.
Example 1
- Input:
- a = [4,8,15,16,23]b = {"values":[42,7],"joinParam":0,"joinIndex":3}
- Output:
- 3
- Explanation:
The second route has its own stops 42 and 7, then joins the first route at its node holding 16; this shared node is returned.
Example 2
- Input:
- a = [1,3,5], b = [2,4,6]
- Output:
- null
- Explanation:
The chains share no node at all, so the answer is null.
Constraints
0 ≤ length of each chain ≤ 105
1 ≤ node value ≤ 105
Neither chain contains a loop
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(1)