Нахождение пересекающегося узла из двух пересекающихся связанных списков

Question

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

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

• m = n,
• m
• м> н

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

Какой самый эффективный способ найти пересекающийся узел?

Answer 1

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

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

---

Редактировать: см. http://richardhartersworld.com/cri/2008/linkedlist.html

Answer 2

Если возможно, вы можете добавить поле 'color' или аналогичное для узлов. Перебирайте один из списков, раскрашивая узлы по мере продвижения. Затем переберите второй список. Как только вы достигнете уже окрашенного узла, вы найдете пересечение.

Answer 3

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

Answer 4

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

Answer 5

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

1. Рекурсивно итерируйте до конца обоих списков, затем посчитайте с конца для шага 2. Обратите внимание, что list_N ударит null до list_M, для M > N
2. Та же длина M=N пересекается, когда list_M != list_N && list_M.next == list_N.next
3. Различные длины 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;
}

Answer 6

Это сумасшедшее решение, которое я нашел во время кодирования поздно ночью, оно в 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.

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