Функция упорядочения маршрутов билетов

Условие

Дан массив tickets, содержащий набор несвязанных билетов. Каждый билет – объект с полями from (откуда) и to (куда). Требуется написать функцию sortTickets(tickets), которая переставит элементы массива так, чтобы получилась последовательность перемещений путешественника от начального города до конечного.

Условия задачи:

• Гарантируется, что из всех билетов образуется один непрерывный путь без замыканий.
• Алгоритм должен работать за линейное время O(N).
• Ограничения по дополнительной памяти отсутствуют.

Результатом работы функции должен стать массив билетов, отсортированный в порядке следования маршрута.

const tickets = [
  { from: 'Калининград', to: 'Челябинск' },
  { from: 'Москва', to: 'Калининград' },
  { from: 'Пятигорск', to: 'Краснодар' },
  { from: 'Челябинск', to: 'Астана' },
  { from: 'Краснодар', to: 'Москва' },
];

Ответ

Постройте таблицу билетов по from и набор всех to. Начальный город — тот from, которого нет среди to; затем последовательно переходите по таблице.

function sortTickets(tickets) {
  if (!tickets.length) return [];
  const byFrom = new Map(tickets.map(ticket => [ticket.from, ticket]));
  const destinations = new Set(tickets.map(ticket => ticket.to));
  const first = tickets.find(ticket => !destinations.has(ticket.from));
  if (!first || byFrom.size !== tickets.length) throw new Error('Не простой маршрут');
  const result = [];
  let current = first;
  while (current && result.length < tickets.length) {
    result.push(current);
    current = byFrom.get(current.to);
  }
  if (current || result.length !== tickets.length) throw new Error('Разрыв или цикл');
  return result;
}

Для примера старт — Пятигорск, финиш — Астана. Используется гарантия единственного пути без повторных исходящих городов; это не общий поиск эйлерова пути. Ожидаемое время O(n), память O(n), исходный массив не меняется.