1
class Solution {
2
  LinkedList<String> res = new LinkedList<>();
3

4
  public List<String> findItinerary(List<List<String>> tickets) {
5
    HashMap<String, PriorityQueue<String>> map = new HashMap<>();
6
    for (int i = 0; i < tickets.size(); i++) {
7
      String a = tickets.get(i).get(0);
8
      String b = tickets.get(i).get(1);
9
      if (!map.containsKey(a)) {
10
        PriorityQueue<String> temp = new PriorityQueue();
11
        map.put(a, temp);
12
      }
13
      map.get(a).add(b);
14
    }
15

16
    dfs("JFK", map);
17
    return res;
18
  }
19

20
  private void dfs(String departure, HashMap<String, PriorityQueue<String>> map) {
21
    PriorityQueue<String> arrivals = map.get(departure);
22
    while (arrivals != null && !arrivals.isEmpty()) {
23
      dfs(arrivals.poll(), map);
24
    }
25
    res.addFirst(departure);
26
  }
27
}