160. Пересечение двух связанных списков (Intersection of Two Linked Lists)

Задание.

Получены указатели двух односвязных списков headA и headB

Верните узел, в котором два списка пересекаются. Если два связанных списка вообще не пересекаются, верните значение null.

Например, следующие два связанных списка начинают пересекаться в узле c1:

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

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

Обычная экспертиза

Входные данные для экпсертизы предоставляются следующим образом (вашей программе эти входные данные не предоставляются):

• intersectVal – значение узла, в котором происходит пересечение. Это равно 0, если нет пересекающегося узла.

• listA – Первый связанный список.

• listB – Второй связанный список.

• skipA – количество узлов, которые нужно пропустить вперед в listA (начиная с заголовка), чтобы добраться до пересекаемого узла.

• skipB – количество узлов, которые нужно пропустить вперед в listB (начиная с заголовка), чтобы добраться до пересекаемого узла.

Затем эксперт создаст связанную структуру на основе этих входных данных и передаст два заголовка, headA и headB в вашу программу. Если вы правильно вернете пересеченный узел, то ваше решение будет принято.

Пример 1.

Входные данные: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Результат: Пересечение в узле 8

Пример 2.

Входные данные: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Результат: Пересечение в узле 2

Пример 3.

Входные данные: head = [1], pos = -1

Результат: NULL, нет пересечений

Решение.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL) return NULL;
        ListNode *a = headA, *b = headB;
        while(a != b){
            a = (a == NULL) ? headB : a->next;
            b = (b == NULL) ? headA : b->next;
        } 
        return a;
    }
};

Способ решения.

Для поиска узла пересечения используются два указателя.

Первоначально указатели позиционируются на начало списков.

Списки разной длины. Для поиска узла пересечения, списки просматриваются дважды. При достижении конца списка, указатель первого списка перенаправляется на второй список, а указатель второго – не первый. Таким образом, если в списках есть пересечение, то оно будет обнаружено на втором проходе.

Если m – длина списка a, а n – длина списка b, то в худшем случае первый указатель просмотрит m+n элементов, а второй указатель просмотрит n+m эелементов, то есть – оба указателя просмотрят одинаковое количетво элементов и, в конце концов, если пересечений нет, оба станут NULL при завершении второго прохода.