7. Intersection of Two Linked Lists
«Две разные дороги, пройденные до конца и начатые снова на чужом пути, непременно сойдутся в точке общего истока».
— Анри Пуанкаре
Точка слияния двух миров
В реальном системном программировании переиспользование динамической памяти — стандарт оптимизации. В системе контроля версий Git различные ветки разработки делят общие цепочки родительских коммитов; в LRU-кэшах различные ключи могут указывать на единый базовый дескриптор в памяти для экономии RAM.
В терминах структур данных это означает, что два независимых связных списка в определенный момент физически сходятся в один узел и дальше продолжают путь как единое целое.
Задача Intersection of Two Linked Lists (LeetCode 160) требует найти точный узел слияния двух списков. Если списки не пересекаются, необходимо вернуть nil.
Интервьюер ожидает от кандидата уровня Middle+/Senior решение с линейным временем $O(N + M)$ и строго константной памятью $O(1)$ без аллокаций в куче.
Архитектура: Симметрия путей против наивных решений
Главная трудность задачи — разная длина непересекающихся частей.
- Список A: $a_1 \to a_2 \to c_1 \to c_2 \to c_3$
- Список B: $b_1 \to b_2 \to b_3 \to c_1 \to c_2 \to c_3$
Точка пересечения — узел $c_1$. Но если просто запустить два указателя параллельно, указатель $A$ придет в $c_1$ на 3-м шаге, а указатель $B$ — только на 4-м. Они разминутся во времени.
Математический триумф: Выравнивание путей перекрестным обходом
Обозначим:
- $L_A$ — длина уникальной части списка A до пересечения.
- $L_B$ — длина уникальной части списка B до пересечения.
- $C$ — длина общего разделяемого сегмента.
Полный путь A: $L_A + C$. Полный путь B: $L_B + C$.
Разница путей: $|L_A - L_B|$.
Как ликвидировать эту разницу без вычисления длин?
Пусть каждый указатель, дойдя до конца своего списка (nil), перепрыгивает на голову чужого списка!
- Указатель
ptrAпройдет: $L_A + C + L_B$. - Указатель
ptrBпройдет: $L_B + C + L_A$.
Поскольку сложение коммутативно ($L_A + C + L_B = L_B + C + L_A$), оба указателя пройдут абсолютно одинаковое расстояние! Они окажутся в узле $c_1$ в один и тот же такт времени.
flowchart TD
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
subgraph DualPath["Симметричный перекрестный обход"]
PA["ptrA стартует в Head A"]:::entry --> WalkA["Идет по A: La + C"]:::process
WalkA --> SwitchA{"ptrA == nil?"}:::warning
SwitchA -->|"Да: переход"| ToHeadB["ptrA = Head B<br>(идет по Lb)"]:::process
PB["ptrB стартует в Head B"]:::entry --> WalkB["Идет по B: Lb + C"]:::process
WalkB --> SwitchB{"ptrB == nil?"}:::warning
SwitchB -->|"Да: переход"| ToHeadA["ptrB = Head A<br>(идет по La)"]:::process
ToHeadB --> Meet["Встреча: ptrA == ptrB<br>Точка пересечения c1!"]:::success
ToHeadA --> Meet
end
Идиоматичный Go-код
package list
// getIntersectionNode находит узел физического пересечения двух списков за O(N + M) и O(1) памяти.
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
ptrA := headA
ptrB := headB
// Крутим цикл, пока указатели не укажут на одну и ту же физическую ячейку памяти
for ptrA != ptrB {
// Если ptrA уперся в конец списка A, переключаем его на старт списка B
if ptrA == nil {
ptrA = headB
} else {
ptrA = ptrA.Next
}
// Если ptrB уперся в конец списка B, переключаем его на старт списка A
if ptrB == nil {
ptrB = headA
} else {
ptrB = ptrB.Next
}
}
// Либо узел пересечения, либо nil (если списки не пересекаются)
return ptrA
}
Взгляд под капот: Mechanical Sympathy
1. Физика сравнения указателей ptrA != ptrB
В Go тип *ListNode — это чистое 64-битное значение виртуального адреса. Оператор ptrA != ptrB компилируется в одну процессорную инструкцию CMP между регистрами CPU.
Здесь нет тяжелых вызовов equals() или сравнения полей структуры. Даже если узлы содержат одинаковые числа Val = 42, но находятся в разных аллокациях, они не равны. Мы ищем точное слияние графа в одном адресе RAM.
2. Что происходит, если списки НЕ пересекаются?
Логичный вопрос интервьюера: «Не уйдет ли код в бесконечный цикл, если общих узлов нет?»
Нет, никогда.
Оба указателя сделают ровно $L_A + L_B$ шагов. На последнем шаге ptrA дойдет до конца списка B и станет nil, а ptrB дойдет до конца списка A и тоже станет nil.
Сработает условие nil == nil (в Go это истинное равенство), цикл завершится, и функция корректно вернет nil.
3. Предсказатель переходов CPU (Branch Predictor)
Внутри цикла проверка if ptrA == nil истинна ровно один раз за весь обход (в момент переключения на другой список). В 99.9% тактов процессорный предсказатель ветвлений спекулятивно выбирает ветку ptrA = ptrA.Next, обеспечивая максимальную пропускную способность конвейера инструкций без пауз на Pipeline Flush.
Альтернативный подход: Выравнивание через дельту длин ($\Delta L$)
Если интервьюер предпочитает строго алгоритмический подход без «прыжков» по спискам:
- Вычисляем длину первого списка $L_A$ и второго $L_B$.
- Находим разницу $\Delta = |L_A - L_B|$.
- Указатель более длинного списка сдвигаем вперед на $\Delta$ шагов.
- Теперь до точки пересечения обоим указателям осталось пройти ровно одинаковое расстояние. Двигаем их параллельно: первый же узел, где
ptrA == ptrB, и есть пересечение.
Этот вариант требует чуть больше строк кода, но работает за аналогичные $O(N + M)$ времени и $O(1)$ памяти.
Итог
Задача Intersection of Two Linked Lists — образец математической симметрии в коде. Объединение двух траекторий превращает разность длин в нулевую дельту, решая задачу за честное $O(1)$ по памяти.
Теперь, когда в нашем арсенале есть разворот, поиск середины и слияние, соберем их в комплексный алгоритм, решающий одну из самых красивых задач на переупорядочивание памяти: 8. Reorder List.