Задача 13: Пересечение двух связанных списков

Напишите определение функции def get_intersection_node(headA, headB), которая принимает два заголовка одиночно связанных списков headA и headB. Функция должна возвращать узел, в котором два списка пересекаются. Если два связанных списка вообще не пересекаются, функция должна вернуть None.

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

Что такое одиночно связанный список?

Одиночно связанный список — это структура данных, где каждый узел содержит два элемента:

1. Значение текущего узла (val).
2. Ссылку на следующий узел в списке (next), либо None, если это последний узел.

Пример реализации:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

Пример создания связанного списка:

node3 = ListNode(3)  # Узел со значением 3, следующий узел отсутствует
node2 = ListNode(2)  # Узел со значением 2
node2.next = node3   # Узел node2 указывает на node3
node1 = ListNode(1)  # Узел со значением 1
node1.next = node2   # Узел node1 указывает на node2

# Список выглядит так: 1 -> 2 -> 3 -> None

Примеры работы функции

Пример 1:

Входные данные:

listA = [4, 1, 8, 4, 5]  
listB = [5, 6, 1, 8, 4, 5]  
Пересечение: 8

Схема:

listA: 4 -> 1 -> 8 -> 4 -> 5  
                 ↘  
listB:      5 -> 6 -> 1  

Ожидаемый результат: Узел со значением 8.

Подробное пояснение:

1. Описание структуры списков:
   • listA начинается с узлов 4 -> 1, затем идет узел со значением 8, после чего узлы 4 -> 5.
   • listB начинается с узлов 5 -> 6 -> 1, затем пересекается с listA на узле со значением 8. После этого оба списка продолжают иметь общие элементы 8 -> 4 -> 5.
2. Процесс работы функции:
   • Функция идет по listA и listB, чтобы найти узел, на котором списки пересекаются.
   • Узлы с одинаковыми значениями в списках (например, 1) не являются пересечением, так как они находятся в разных местах памяти. Пересечение подтверждается, если узлы указывают на одно и то же место в памяти.
3. Результат:
   • Узел со значением 8 — это первая точка, где listA и listB пересекаются. После этого узла списки совпадают.

Пример 2:

Входные данные:

listA = [1, 9, 1, 2, 4]  
listB = [3, 2, 4]  
Пересечение: 2  

Схема:

listA: 1 -> 9 -> 1 -> 2 -> 4  
                      ↘  
listB:           3 -> 2 -> 4  

Ожидаемый результат: Узел со значением 2.

Подробное пояснение:

1. Описание структуры списков:
   • listA начинается с узлов 1 -> 9 -> 1, затем идет узел со значением 2, после чего узел 4.
   • listB начинается с узлов 3, затем идет пересечение с listA на узле со значением 2, после чего оба списка имеют общие элементы 2 -> 4.
2. Процесс работы функции:
   • Функция проверяет узлы listA и listB по очереди, сравнивая их местоположение в памяти.
   • Пересечение найдено на узле со значением 2, так как он является общей точкой для обоих списков.
3. Результат:
   • Узел со значением 2 — это первая точка пересечения. После этого узла списки совпадают.