Unicorns OA 面试真题解析：根据登机牌还原行程（Reconstruct Itinerary）

Given the following list of boarding passes, write some code which returns the itinerary of the trip.

Boarding passes:

SYD -> LAX
LHR -> DEL
SFO -> JFK
DEL -> PEK
JFK -> LHR
PEK -> SYD

Expected result:

SFO
JFK
LHR
DEL
PEK
SYD
LAX

这道题要求根据一组登机牌还原完整行程，本质上是把“出发地 -> 目的地”的有向边串成一条唯一的路径。关键思路是先统计每个城市的入度和出度，找到唯一的起点：它通常是出度比入度多 1 的城市。然后沿着映射不断向后追踪，依次输出城市即可。题目示例中，SFO 是起点，按 SFO -> JFK -> LHR -> DEL -> PEK -> SYD -> LAX 的顺序即可得到完整行程。这个题常见于图、哈希表和链式路径恢复场景。