重新安排行程

/*
 * 思路：
 * 1. 将所有航班票按照出发地为键，目的地为值放入一个Map中，值为一个优先队列，方便按字典序排序。
 * 2. 使用DFS从JFK开始构建行程，每次选择字典序最小的航班。
 * 3. 使用LinkedList将行程存储，因为DFS后行程是逆序的，使用LinkedList的addFirst方法可以避免最后反转列表。
 */
import java.util.*;
import java.util.stream.Collectors;
 
public class SolutionStream {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> flights = tickets.stream()
            .collect(Collectors.groupingBy(
                ticket -> ticket.get(0), 
                Collectors.mapping(
                    ticket -> ticket.get(1), 
                    Collectors.toCollection(PriorityQueue::new)
                )
            ));
        LinkedList<String> itinerary = new LinkedList<>();
        dfs("JFK", flights, itinerary);
        return itinerary;
    }
 
    private void dfs(String airport, Map<String, PriorityQueue<String>> flights, LinkedList<String> itinerary) {
        PriorityQueue<String> destinations = flights.get(airport);
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll(), flights, itinerary);
        }
        itinerary.addFirst(airport);
    }
}