найти один и тот же узел из двух связанных списков. Не могу использовать хеш, Не может быть сложности O (n ^ 2)

Question

найти один и тот же узел из двух связанных списков. Не может использовать хеш, Не может быть сложности O (n ^ 2).

Пожалуйста, дайте несколько советов. Большое спасибо.

Answer 1

Сортируйте два связанных списка, а затем выполните линейный проход, чтобы найти два равных узла. Это 2 * O (NlogN) + 2 * O (N) = O (NlogN).