¿Cómo encontrar el elemento medio de la lista vinculada en una sola pasada?

12

Una de las preguntas más populares de las estructuras de datos y el algoritmo, formulada principalmente en entrevistas telefónicas.

Gilles 'SO- deja de ser malvado'
fuente
55
Si las respuestas presentadas en este hilo son las que esperaba el entrevistador, entonces esta pregunta no prueba la capacidad técnica, sino qué tan bien el candidato puede esquivar como un abogado.
G. Bach
2
Esta es una pregunta de entrevista terrible porque depende críticamente del término " pasar ", que es vago, ambiguo, subjetivo. Casi todas las buenas respuestas a esta pregunta implican abusar de la definición para que pueda ignorarla efectivamente.
RBarryYoung
2
Bueno, la pregunta plantea muchas discusiones aquí. Eso significa que es una buena pregunta de entrevista en un aspecto: te hace pensar.
Hendrik ene
3
Quiero responder "leer todos los elementos en un vector, luego acceder al elemento en el tamaño de posición () / 2"
Cort Ammon
1
@HendrikJan En realidad, creo que es una pregunta de entrevista completamente terrible. Primero, es probable que conduzca a discusiones sobre lo que significa exactamente "de una pasada", en lugar de una discusión productiva. En segundo lugar, un candidato podría encontrar la respuesta "correcta" y luego rechazarla porque pensaba que violaba el criterio "de una pasada". Tercero, debido a que es una pregunta bien conocida, es una mejor prueba de "¿Conoces preguntas populares de entrevistas?" que "¿Eres un buen candidato para este trabajo?" Cualquiera de esos debería ser suficiente para hundir esto como una pregunta; los tres simultáneamente son un desastre.
David Richerby

Respuestas:

24

Haciendo trampa, y haciendo dos pases al mismo tiempo, en paralelo. Pero no sé si a los reclutadores les gustará esto.

Se puede hacer en una sola lista vinculada, con un buen truco. Dos punteros recorren la lista, uno con doble velocidad. Cuando el rápido llega al final, el otro está a medio camino.

Hendrik Jan
fuente
1
Sí, no está claro si este es un solo pase. La pregunta no está clara sobre ese punto.
David Richerby
2
Por cierto, esto está relacionado con el rompecabezas en el que tienes dos velas, una hora encendidas cada una, y se te pide que midas 45 minutos.
Hendrik ene
2
¿Es esto realmente diferente de iterar la lista, contar elementos y luego iterar por segunda vez hasta la mitad? Todo lo que es diferente es cuando iteras la mitad extra. Como @RBarryYoung menciona en la otra respuesta similar, realmente no es un solo pase, es un pase y medio.
2
Si la lista es larga, mover ambos punteros "en paralelo" generará menos errores de caché que iterar desde el principio por segunda vez.
zwol
2
Utiliza el mismo principio que el algoritmo de tortuga y liebre para la detección de ciclos.
Joshua Taylor
7

Si no es una lista doblemente enlazada, podría contar y usar una lista, pero eso requiere duplicar su memoria en el peor de los casos, y simplemente no funcionará si la lista es demasiado grande para almacenarla en la memoria.

Una solución simple, casi tonta, es simplemente incrementar el nodo medio cada dos nodos

function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}
00500005
fuente
Su segunda opción es la respuesta correcta (en mi humilde opinión, por supuesto).
Matthew Crumley el
1
En realidad, está haciendo 1 1/2 pasos sobre la lista vinculada.
RBarryYoung
6

Elaborando sobre la respuesta de Hendrik

Si se trata de una lista doblemente vinculada, itere desde ambos extremos

function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

Dado [1, 2, 3] => 2

1, 3
1, 2
2, 2

Dado [1, 2] => 1

1, 2
1, 1

Dado [1] => 1

Dado [] => null

00500005
fuente
¿Cómo es esto eficiente? También está iterando n veces y no n / 2.
Karan Khanna
3

Cree una estructura con un puntero capaz de apuntar a los nodos de la lista vinculada y con una variable entera que cuente el número de nodos en la lista.

struct LL{
    struct node *ptr;
    int         count;
}start;

start.ptrstart.count=1
start.count

start.count

Prateek
fuente
-2

Cree una matriz dinámica, donde cada elemento de la matriz sea un puntero a cada nodo en la lista en orden de desplazamiento, comenzando desde el principio. Cree un número entero, inicializado en 1, que realice un seguimiento de cuántos nodos ha visitado (que se incrementa cada vez que va a un nuevo nodo). Cuando llegue al final, sabrá qué tan grande es la lista y tiene una matriz ordenada de punteros para cada nodo. Finalmente, divida el tamaño de la lista por 2 (y reste 1 para la indexación basada en 0) y busque el puntero que se encuentra en ese índice de la matriz; Si el tamaño de la lista es impar, puede elegir qué elemento devolver (todavía devolveré el primero).

Aquí hay un código Java que hace que el punto se transmita (aunque la idea de una matriz dinámica será un poco inestable). Proporcionaría C / C ++ pero estoy muy oxidado en esa área.

public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}
Andonaeus
fuente
-3

¿Se considera la recursión más de un pase?

Recorre la lista hasta el final, pasando un número entero por referencia. Haga una copia local de ese valor en cada nivel para referencia posterior, e incremente el recuento de referencia en la próxima llamada.

En el último nodo, divida el recuento entre dos y trunca / floor () el resultado (si desea que el primer nodo sea el "medio" cuando solo hay dos elementos) o redondee hacia arriba (si desea que el segundo nodo sea la mitad"). Use un índice basado en cero o en uno apropiadamente.

Desenrollado, haga coincidir el recuento de referencias con la copia local (que es el número del nodo). Si es igual, devuelve ese nodo; de lo contrario, devuelve el nodo devuelto por la llamada recursiva.
.

Hay otras formas de hacer esto; algunos de ellos pueden ser menos engorrosos (pensé que vi a alguien decir leerlo en una matriz y usar la longitud de la matriz para determinar las felicitaciones del medio). Pero, francamente, no hay buenas respuestas, porque es una pregunta estúpida de entrevista. Número uno, que todavía usa listas vinculadas ( opinión de apoyo ); Dos, encontrar el nodo intermedio es un ejercicio académico arbitrario sin valor en escenarios de la vida real; Tres, si realmente necesitara conocer el nodo medio, mi lista vinculada expondría un recuento de nodos. Es mucho más fácil mantener esa propiedad que perder el tiempo recorriendo toda la lista cada vez que quiero el nodo central. Y finalmente, cuatro, a cada entrevistador le gustarán o rechazarán diferentes respuestas: lo que un entrevistador piensa que es hábil, otro lo llamará ridículo.

Casi siempre respondo las preguntas de la entrevista con más preguntas. Si recibo una pregunta como esta (nunca la tengo), le preguntaría (1) ¿Qué está almacenando en esta lista vinculada? ¿Existe una estructura más apropiada para acceder de manera eficiente al nodo medio si es realmente necesario hacerlo? ; (2) ¿Cuáles son mis limitaciones? Puedo hacerlo más rápido si la memoria no es un problema (por ejemplo, la respuesta de la matriz), pero si el entrevistador cree que aumentar la memoria es un desperdicio, me molestarán. (3) ¿En qué idioma desarrollaré? Casi todos los idiomas modernos que conozco tienen clases integradas para lidiar con listas vinculadas que hacen innecesario recorrer la lista: ¿por qué reinventar algo que los desarrolladores del lenguaje han ajustado para la eficiencia?

James K
fuente
66
No sabe quién votó en contra, por lo que su conclusión de que una persona votó en contra de todo puede ser cierta o no, pero ciertamente no tiene base en los hechos disponibles para usted. Pero estoy rechazando su respuesta porque estamos buscando explicaciones, no montones de código.
David Richerby
Puede ser una suposición, pero cuando miro un momento y menos de 30 segundos después cada publicación tiene exactamente -1, no es irrazonable. Incluso si fueron 5 o 6 personas diferentes, ninguno de ellos dejó un comentario por qué. Pero gracias por al menos indicar una razón. No entiendo por qué una explicación prolija es mejor que el código: sí, es para una entrevista telefónica, pero no le estoy dando al OP una respuesta enlatada para regurgitar, le estoy mostrando una manera de hacerlo. Es decir, creo que rechazar una publicación porque tiene código no está disponible, pero gracias por al menos decir por qué lo hiciste.
James K
Punto justo: no se me había ocurrido que se podía saber el momento de los votos (creo que tener la página cargada mientras ocurrieron es la única forma en que los usuarios comunes como nosotros podrían averiguarlo). Tenemos un par de meta publicaciones sobre por qué intentamos evitar el código real aquí: (1) (2) .
David Richerby
Gracias por los meta enlaces. Leí las preguntas frecuentes, pero no vi nada allí, no es que hubiera notado algo así, lo más probable, no algo que hubiera esperado. Pero tampoco pude encontrar nada cuando volví a revisar después de ser comido. Puede que todavía lo esté pasando por alto, pero lo miré. El razonamiento en los meta posts tiene sentido; Gracias por la respuesta.
James K
-5

Mediante el uso de 2 punteros. Incremente uno en cada iteración y otro en cada segunda iteración. Cuando el primer puntero apunta al final de la lista vinculada, el segundo puntero apunta al modo medio de la lista vinculada.

b dharuni
fuente
Esto simplemente duplica la respuesta de Hendrick . Por favor no responda a menos que tenga algo nuevo que decir.
David Richerby