Наилучший возможный алгоритм для проверки, объединяются ли два связанных списка в какой-либо момент?Если да, то где?[дубликат]

Question

Возможный Дубликат:
Связанный список вопросов для интервью

Это вопрос для интервью, на который у меня нет ответа.Учитывая Два списка, вы не можете изменить список и не знаете его длину.Дайте наилучший возможный алгоритм для:

1. Проверьте, не сливаются ли два списка в какой-либо момент?
2. Если происходит слияние, то в какой момент они сливаются?
3. Если я позволю вам изменить список, как бы вы изменили свой алгоритм?

Answer 1

Я предполагаю, что мы говорим о простых связанных списках, и мы можем безопасно создать хэш-таблицу указателей элементов списка.

Q1:Выполните итерацию до конца обоих списков, если соответствующие последние элементы совпадают, списки в какой-то момент объединятся.

Сложность - O(N), пространственная сложность - O(1)

Q2:

1. Поместите все элементы одного списка в хэш-таблицу
2. Выполните итерацию по 2-му списку, проверяя хэш-таблицу для каждого элемента списка.Первое попадание (если таковое имеется) - это точка слияния, и у нас есть позиция во 2-м списке.
3. Чтобы получить позицию в 1-м списке, снова выполните итерацию по первому списку в поисках элемента, найденного на предыдущем шаге.

Временная сложность - O(N).Космическая сложность - O(N)

Q3:

1. Как Q1, но также измените направление указателей списка на обратное.
2. Затем выполните итерацию по перевернутым спискам в поисках последнего общего элемента - то есть точки слияния - и восстановите список в исходном порядке.

Временная сложность - O(N).Космическая сложность - O(1)

Answer 2

Номер 1: просто итерируйте оба, а затем проверьте, заканчиваются ли они одним и тем же элементом. Это O (n), и он не может быть побежден (поскольку это может быть последний элемент, который является общим, и попадание туда всегда занимает O (n)).

Answer 3

<Ол>

Обходите эти два списка параллельно одним элементом, добавляйте каждый элемент в набор посещенных узлов (может быть хэш-карта или простой набор, вам нужно только проверить, посещали ли вы этот узел ранее). На каждом шаге проверяйте, посещали ли вы этот узел (если да, то это точка слияния), и добавляйте его в набор узлов, если вы посещаете его в первый раз. Другая версия (как указано @reinier) состоит в том, чтобы обходить только первый список, сохранять его узлы в множестве, а затем проверять только второй список по этому множеству. Первый подход быстрее, когда ваши списки объединяются рано, так как вам не нужно хранить все узлы из первого списка. Второе лучше в худшем случае, когда оба списка вообще не объединяются, поскольку в Set не сохраняются узлы из второго списка.

см. 1.

Вместо Set вы можете попытаться пометить каждый узел, но если вы не можете изменить структуру, это не так полезно. Вы также можете попробовать отсоединить каждый посещенный узел и связать его с каким-нибудь защитным узлом (который вы проверяете на каждом шаге, встречались ли вы во время обхода). Это экономит память для Set, если список достаточно длинный.

Answer 4

Обходите список и найдите глобальную переменную для поиска числа обнаруженных NULL . Если в какой-то момент они объединятся, будет только 1 NULL , в противном случае будет два NULL .