Поиск пересекающихся node из двух пересекающихся связанных списков

Предположим, что есть два одинаково связанных списка, оба из которых пересекаются в какой-то точке и становятся единым связанным списком.

Указатели головы или начала обоих списков известны, но пересекающийся node не известен. Кроме того, количество узлов в каждом списке перед их пересечением неизвестно, и оба списка могут иметь его разные, то есть List1 может иметь n узлов до того, как он достигнет точки пересечения, а List2 может иметь m узлов, прежде чем он достигнет точки пересечения, где m и n могут быть

m = n,
m < n или
m > n

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

Каков наиболее эффективный способ нахождения пересекающихся node?

Ответ 1

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

Переместите два связанных списка, чтобы найти M и N.
Вернитесь к головам, затем перейдите | M & minus; N | узлы в более длинном списке.
Теперь пройдите шаг блокировки и сравните узлы, пока не найдете общие.

Изменить: см. http://richardhartersworld.com/cri/2008/linkedlist.html

Ответ 2

Если возможно, вы можете добавить поле "color" или аналогично узлам. Итерации по одному из списков, раскрашивание узлов по ходу. Затем перебираем второй список. Как только вы достигнете node, который уже окрашен, вы нашли пересечение.

Ответ 3

Сбросьте содержимое (или адрес) обоих списков в одну хеш-таблицу. Первое столкновение - это ваше пересечение.

Ответ 4

Проверьте последние узлы каждого списка. Если есть пересечение, их последний node будет таким же.

Ответ 5

Это сумасшедшее решение, которое я нашел во время кодирования поздно ночью, он в 2 раза медленнее, чем принятый ответ, но использует хороший арифметический взлом:

public ListNode findIntersection(ListNode a, ListNode b) {
    if (a == null || b == null)
        return null;

    int A = a.count();
    int B = b.count();

    ListNode reversedB = b.reverse();

    // L = a elements + 1 c element + b elements
    int L = a.count();

    // restore b
    reversedB.reverse();

    // A = a + c
    // B = b + c
    // L = a + b + 1

    int cIndex = ((A+B) - (L-1)) / 2;
    return a.atIndex(A - cIndex);
}

Мы разбиваем списки на три части: a это часть первого списка до начала общей части, b это часть второго списка, пока общая часть и c, которая является общей частью двух списки. Мы подсчитываем размеры списка, а затем обратный список b, это приведет к тому, что при запуске списка перемещения из a конец мы закончим на reversedB (мы поедем a -> firstElementOfC -> reversedB). Это даст нам три уравнения, позволяющие получить длину общей части c.

Это слишком медленно для соревнований по программированию или используется в производстве, но я думаю, что этот подход интересен.

Ответ 6

Возможно, в данный момент это не имеет значения, но здесь мой грязный рекурсивный подход. Это занимает время O(M) и O(M), где M >= N для list_M длины M и list_N длины N

Рекурсивно итерации до конца обоих списков, затем подсчитываем с конца для шага 2. Обратите внимание, что list_N достигнет null до list_M, для M > N
Те же длины M=N пересекаются, когда list_M != list_N && list_M.next == list_N.next
Различные длины M>N пересекаются, когда list_N != null

Пример кода:

Node yListsHelper(Node n1, Node n2, Node result) {
    if (n1 == null && n2 == null)
        return null;
    yLists(n1 == null ? n1 : n1.next, n2 == null ? n2 : n2.next, result);
    if (n1 != null && n2 != null) {
        if (n2.next == null) { // n1 > n2
            result.next = n1;
        } else if (n1.next == null) { // n1 < n2
            result.next = n2;
        } else if (n1 != n2 && n1.next == n2.next) { // n1 = n2
            result.next = n1.next; // or n2.next
        }
    }
    return result.next;
}