doubly - simple linked list c

Encontrar el nodo de intersección de dos listas vinculadas que se cruzan

Question

Supongamos que hay dos listas conectadas de forma individual, que se cruzan en un punto y se convierten en una única lista vinculada.

Se conocen los punteros de inicio o de inicio de ambas listas, pero no se conoce el nodo de intersección. Además, se desconoce el número de nodos en cada lista antes de que se crucen y ambas listas pueden tenerlo diferente, es decir, List1 puede tener n nodos antes de llegar al punto de intersección y List2 puede tener m nodos antes de llegar al punto de intersección donde myn pueden ser

• m = n,
• m <n o
• m> n

Una solución conocida o fácil es comparar cada puntero de nodo en la primera lista con cada otro puntero de nodo en la segunda lista mediante el cual los punteros de nodo coincidentes nos llevarán al nodo de intersección. Pero, la complejidad del tiempo en este caso será O (n ² ), que será alta.

¿Cuál es la forma más eficiente de encontrar el nodo que se cruza?

Answer 1

Si es posible, puede agregar un campo ''color'' o similar a los nodos. Itera sobre una de las listas, coloreando los nodos sobre la marcha. Luego itera sobre la segunda lista. Tan pronto como llegue a un nodo que ya está coloreado, ha encontrado la intersección.

Answer 2

Verifique los últimos nodos de cada lista, si hay una intersección, su último nodo será el mismo.

Answer 3

Vuelque el contenido (o la dirección) de ambas listas en una tabla hash. primera colisión es tu intersección.

Answer 4

Esto toma O (M + N) tiempo y O (1) espacio, donde M y N son la longitud total de las listas enlazadas. Tal vez ineficiente si la parte común es muy larga (es decir, M, N >> m, n)

1. Recorre las dos listas enlazadas para encontrar M y N.
2. Vuelva a las cabezas, luego recorra | M - N | nodos en la lista más larga.
3. Ahora camine en el paso de bloqueo y compare los nodos hasta que encuentre los comunes.

Editar: ver http://richardhartersworld.com/cri/2008/linkedlist.html

Answer 5

Esta es una solución loca que encontré al programar a altas horas de la noche, es 2 veces más lenta que la respuesta aceptada pero usa un buen truco aritmético:

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);
}

Dividimos las listas en tres partes: a esta es parte de la primera lista hasta el comienzo de la parte común, b esta es parte de la segunda lista hasta la parte común c que es parte común de dos listas. Contamos los tamaños de lista y luego la lista inversa b , esto hará que cuando comencemos la lista de desplazamiento desde a extremo, terminaremos en reversedB (iremos a a -> firstElementOfC -> reversedB ). Esto nos dará tres ecuaciones que nos permiten obtener la longitud de la parte común c .

Esto es demasiado lento para programar competiciones o usarlo en producción, pero creo que este enfoque es interesante.

Answer 6

Tal vez sea irrelevante en este momento, pero aquí está mi sucia aproximación recursiva. Esto toma O(M) tiempo y O(M) espacio, donde M >= N para list_M de longitud M y list_N de longitud N

1. Repita recursivamente hasta el final de ambas listas, luego cuente desde el final para el paso 2 . Tenga en cuenta que list_N llegará a null antes de list_M , para M > N
2. Mismos largos M=N cruzan cuando list_M != list_N && list_M.next == list_N.next
3. Diferentes longitudes M>N cruzan cuando list_N != null

Ejemplo de código:

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;
}