Связанный список: Нахождение пересечения двух связанных списков путем замены их указателей после достижения конца одного из них.

Question

Этот вопрос касается особого подхода к нахождению пересечения, а НЕ общего способа сделать это.Вначале мой подход к решению проблемы заключался в том, что Кентим ответил на этот вопрос .Его ответ цитируется ниже.

Это занимает время O (M + N) и пространство O (1), где M и N - общая длина связанных списков.Может быть неэффективным, если общая часть очень длинная (т. Е. M, N >> m, n)

1. Перейдите два связанных списка, чтобы найти M и N.

2. Вернитесь к головам, затем пройдите | M - N |узлы в длинном списке.

3. Теперь перейдите к шагу блокировки и сравните узлы, пока не найдете общие.

Iесть проблемы с пониманием 3-го решения 160.Пересечение двух связанных списков на Leetcode.Подход другой, но я чувствую, что он может быть похож на вышеуказанное решение.Может ли кто-нибудь показать мне, как эти два могут быть похожими?Я до сих пор не вижу, как можно добраться до перекрестка от этого.Представленное решение:

Подход № 3 (два указателя) [Принято]

Поддержание двух указателей pA и pB, инициализированных в заголовках A и B соответственно.Затем позвольте им обоим пройти по спискам, по одному узлу за раз.

Когда pA достигнет конца списка, перенаправьте его на заголовок B (да, B, это верно.);аналогично, когда pB достигает конца списка, перенаправьте его на голову A.

Если в любой точке pA встречает pB, то pA / pB является узлом пересечения.

Чтобы понять, почемуПриведенный выше трюк сработает, рассмотрите следующие два списка: A = {1,3,5,7,9,11} и B = {2,4,9,11}, которые пересекаются в узле '9'.Поскольку B.length (= 4)

Если два списка имеют пересечение, то их последние узлы должны быть одинаковыми.Поэтому, когда pA / pB достигает конца списка, запишите последний элемент A / B соответственно.Если два последних элемента не совпадают, то два списка не имеют пересечений.

Answer 1

Они оба полагаются на то, что указатели расположены на одинаковом расстоянии от перекрестка, а затем направляют их вперед одновременно, пока они не встретятся.

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

Мне нравится второй еще немного, потому что нет точки, в которой вы двигаете только один из указателей вперед, оба указателя перемещаются на каждой итерации.Первый может быть более обобщенным для списков 3+, потому что вам придется полностью проходить каждый список только один раз.