企业官网建设流程全解析

Core idea: Hierholzer’s algorithm for an Eulerian path. A naive lexical greedy walk can get stuck (e.g.
“JFK→KUL” dead-ends when
“JFK→NRT→JFK→KUL” is the answer). The fix: keep walking greedily, but only append each airport on the way back up — dead-end remnants get spliced in at the right position automatically.

class Solution {
private Map<String, PriorityQueue> graph = new HashMap<>();
private LinkedList route = new LinkedList<>();

public List<String> findItinerary(List<List<String>> tickets) { for (List<String> t : tickets) { graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1)); } dfs("JFK"); return route; } /** Hierholzer: exhaust all outgoing edges, then append on the way back. */ private void dfs(String airport) { PriorityQueue<String> next = graph.get(airport); while (next != null && !next.isEmpty()) { dfs(next.poll()); // edge consumed as we descend } route.addFirst(airport); // post-order -> prepend, no final reverse needed }

}

Key points

“PriorityQueue” per airport gives the lexicographically smallest next hop for free;
“poll()” consumes that exact ticket, so duplicate edges are tracked correctly.

• Post-order prepend is what makes it work: an airport is emitted only after its whole sub-loop is finished, so a cycle discovered later is inserted ahead of the node that leads into it — hence
  “JFK, NRT, JFK, KUL” instead of a dead end.

“route.addFirst” on a
“LinkedList” is
“O(1)”. If you prefer an
“ArrayList”, use
“add” then
“Collections.reverse(route)” at the end — identical result.

• Recursion depth is at most
  “tickets + 1” (≤ ~301 per constraints), so no stack risk here.

Complexity:
“O(m log m)” time — each edge is polled once, heap ops cost
“log(deg)”;
“O(m)” space.

Verified against brute-force enumeration (lexicographically minimum over all valid itineraries) on 20,000 random cases, plus the official samples:
“JFK,MUC,LHR,SFO,SJC”,
“JFK,ATL,JFK,SFO,ATL,SFO”, and the dead-end case
“JFK,NRT,JFK,KUL”. A 300-ticket input runs in ~64 ms.