Preguntas de la entrevista de programación de listas vinculadas

Si está interesado en leer más sobre las preguntas de la entrevista de programación en general, hemos compilado una larga lista de estas preguntas, incluida su explicación ...

Si estás interesado en leer más sobre Preguntas de la entrevista de programación en general, hemos compilado una larga lista de estas preguntas, incluyendo sus explicaciones, implementaciones, representaciones visuales y aplicaciones.

Introducción

Las listas enlazadas son una estructura de datos que representa una colección lineal de nodos. Una característica específica de las listas enlazadas es que el orden de los nodos no está dictado por su presencia en la memoria, sino por los punteros que cada nodo tiene hacia el siguiente nodo en la secuencia.

linked_list
[Representación de una lista enlazada]{.small}

Existen varios tipos de listas enlazadas:

  • Listas enlazadas individualmente - Una lista enlazada clásica, como la que se muestra en la imagen de arriba. Los nodos de las listas enlazadas individualmente contienen un puntero al siguiente nodo de la lista.
  • Listas doblemente enlazadas: este tipo de lista enlazada contiene un puntero al siguiente, pero también un puntero al nodo anterior en la lista.
  • Listas enlazadas circulares: en lugar de contener un puntero nulo al final de la lista, el último nodo de estas listas contiene un puntero al primer nodo, lo que las hace circulares.

Como la lista enlazada es una de las estructuras de datos más básicas e importantes en informática, hemos compilado una lista de preguntas comunes de entrevistas con respecto a las listas enlazadas para este artículo. ¿Necesitas ayuda para estudiar para tu entrevista? Recomendamos probar un servicio como Problema de codificación diaria, que le enviará por correo electrónico preguntas de práctica diariamente.

Inserción y eliminación de nodos {#inserción y eliminación de nodos}

Pregunta de la entrevista {#pregunta de la entrevista}

Elimine el cuarto elemento de la siguiente lista:

1
2->4->5->3->7->0

Inserte un elemento (6) en la 2ª posición de la siguiente lista:

1
2->4->5->3->7->0

Explicación

Comencemos con una tarea simple: insertar un nodo en una lista. Hay algunas maneras en que alguien puede pedirle que haga esto:

  • Insertar al inicio de la lista enlazada
  • Insertar al final de la lista enlazada
  • Inserción en una posición dada

Vamos a cubrirlos uno por uno primero, antes de sumergirnos en el proceso de eliminación de un nodo.

Inserción de nodos

Para insertar un nodo al comienzo de una lista enlazada, simplemente necesitamos cambiar el encabezado actual de la lista enlazada al nuevo nodo que estamos insertando, y también apuntar el nodo insertado al encabezado anterior:

inserting_node_at_beginning

Echemos un vistazo al pseudocódigo:

1
2
3
4
5
6
7
Node newNode

if head is null
    head = newNode

newNode.next = head
head = newNode

Para insertar un nodo al final de una lista enlazada, simplemente necesitamos cambiar el último puntero de null al nuevo nodo:

inserting_node_at_the_end

Echemos un vistazo al pseudocódigo:

1
2
3
4
5
6
Node newNode

last = head;
while(last.next)
    last = last.next
last.next = newNode1

Hacemos esto asignando newNode como encabezado, si la lista está vacía, e iterando hasta el final de la lista si no lo está, agregando nuestro nodo.

Y finalmente, para insertar un nodo en la posición dada, necesitamos establecer el siguiente nodo de la posición dada como el siguiente nodo del nuevo nodo, y asignar el nuevo nodo como el siguiente nodo de la posición dada:

insert_node_at_given_position

Echemos un vistazo al pseudocódigo:

1
2
3
4
5
insertAtPosition(list, node, newNode)

if node is not null
    newNode.next = node.next
    node.next = newNode;

Eliminación de nodos

Lo que tenemos que hacer aquí es recorrer la lista, haciendo un seguimiento del nodo anterior al nodo que queremos eliminar.

Al llegar al nodo que queremos eliminar, apuntamos el nodo anterior al nodo posterior al nodo de destino y eliminamos el nodo de destino:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
removeNode(Node node)
    prevNode = null
    curr = head

    while curr is not null
        if prevNode is null
            head = curr.next
        if curr == node
            prevNode.next = curr.next
            curr = null

    prevNode = curr
    curr = curr.next

Comparación de cadenas representadas como listas enlazadas

Pregunta de la entrevista {#pregunta de la entrevista}

Escriba una función que pueda comparar dos cadenas, representadas como listas enlazadas como:

1
2
List 1: S->T->A->C->K->A->B->U->S->E
List 2: S->T->A->C->K->O->V->E->R->F->L->O->W

La función puede devolver tres valores:

  • 0 - Si las dos listas representan la misma Cadena
  • 1 - Si la primera lista es lexicográficamente mayor que la segunda lista
  • -1 - Si la segunda lista es lexicográficamente mayor que la primera lista

Nota: "Lexicográficamente mayor" significa que una Cadena aparecería después de la otra Cadena según la posición del diccionario.

Si se implementa correctamente, usar esa función en este ejemplo en particular debería producir el siguiente resultado:

1
-1

Explicación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
compare(node1, node2):

    while node and node are not null AND node1.content is equal to node2.content
        node1 = node1.next
        node2 = node2.next

    if node1 and node2 are not null
        if node1.content > node2.content
            return 1
        else
            return -1

    if node1 is not null and node2 is null
        return 1

    if node2 is not null and node1 is null
        return -1

    return 0

list1 = Node('s')
list1.next = Node('t')
list1.next.next = Node('a')
list1.next.next.next = Node('c')
list1.next.next.next.next = Node('k')
list1.next.next.next.next.next = Node('a')
list1.next.next.next.next.next.next = Node('b')
list1.next.next.next.next.next.next.next = Node('u')
list1.next.next.next.next.next.next.next.next = Node('s')
list1.next.next.next.next.next.next.next.next.next = Node('e')

list2 = Node('s')
list2.next = Node('t')
list2.next.next = Node('a')
list2.next.next.next = Node('c')
list2.next.next.next.next = Node('k')
list2.next.next.next.next.next = Node('o')
list2.next.next.next.next.next.next = Node('v')
list2.next.next.next.next.next.next.next = Node('e')
list2.next.next.next.next.next.next.next.next = Node('r')
list2.next.next.next.next.next.next.next.next.next = Node('f')
list2.next.next.next.next.next.next.next.next.next.next = Node('l')
list2.next.next.next.next.next.next.next.next.next.next.next = Node('o')
list2.next.next.next.next.next.next.next.next.next.next.next.next = Node('w')

compare(list1, list2)

El bucle while atraviesa ambas listas con dos condiciones adjuntas:

  • nodo1 y nodo2 no son nulos
  • nodo1.contenido es igual a nodo2.contenido

Esto significa que atravesará ambas listas, nodo por nodo, siempre que no lleguen al final de la lista y cada carácter coincida entre ellos. Si alguna de estas dos condiciones devuelve falso, el ciclo se rompe.

La instrucción if verifica si ambos nodos no son nulos:

  • Si el contenido del primer nodo es mayor que el del segundo nodo, devolvemos 1
  • Si el contenido del segundo nodo es mayor que el del primer nodo, devolvemos -1

Y las últimas dos declaraciones if simplemente devuelven 1 y -1 en consecuencia si los tamaños de la lista no coinciden.

En última instancia, si pasa todas las comprobaciones, significa que las listas coinciden y representan la misma Cadena, devolviendo 0.

Invertir una lista

Pregunta de la entrevista {#pregunta de la entrevista}

Invierta la lista enlazada dada:

1
1->2->3->4->5

Explicación

Hay dos formas de abordar este problema: iterativa y recursiva.

Echemos un vistazo al pseudocódigo iterativo detrás de la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Node prevNode, currNode, nextNode

prevNode = null
nextNode = null
currNode = head

while currNode is not null
    nextNode = currNode.next
    currNode.next = prevNode
    prevNode = currNode
    currNode = nextNode
head = prevNode

reversing_linked_list_gif

Para lograr esto, instanciamos tres nodos: prevNode, nextNode y currNode. Tanto prevNode como nextNode apuntan a nulo, y currNode está configurado para ser el encabezado actual de la lista enlazada.

Se inicia un ciclo while con una condición de terminación de currNode apuntando a nulo, y comienza el proceso de cambio:

  • nextNode se convierte en el siguiente nodo en línea para currNode

  • currNode.next (el siguiente nodo en la línea) apunta a prevNode, que actualmente es nulo

  • prevNode se cambia y ahora apunta a currNode, cambiando sus lugares

  • currNode se cambia y ahora apunta a nextNode, que anteriormente se configuró en el siguiente nodo en línea para currNode. Esto avanza efectivamente el marcador currNode a través de la lista enlazada y comienza el proceso de nuevo.

  • A medida que se mueve el marcador currNode, finalmente llega al final y todos los nodos se han invertido. La condición de terminación se cumple ya que currNode apunta a null y el encabezado se convierte en prevNode, que es el último nodo anterior en la lista enlazada. Dado que todas las referencias están invertidas, para completar la inversión, el encabezado también debe apuntar al ahora primer elemento de la secuencia.

Con eso fuera del camino, echemos un vistazo al pseudocódigo recursivo detrás de la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Node first, rest

Node recursiveReverse(Node current, previous)

    if current.next is null
        head = current
        current.previous = previous
        return
    first = current.next
    current.next = previous

    recursiveReverse(first, current)
    return head

Selección de un nodo aleatorio

Pregunta de la entrevista {#pregunta de la entrevista}

Devuelve un nodo aleatorio de una lista enlazada determinada, asegurándose de que la probabilidad de obtener ese nodo específico sea 1/n, donde n es el tamaño de la lista:

1
1->4->2->5->9->7

Explicación

Hay dos formas de abordar este problema y encontrar una solución:

  • Recorrer la lista y contar sobre la marcha. Luego lo atravesamos de nuevo, seleccionando todos y cada uno de los nodos con probabilidad 1/n antes de generar un número aleatorio de 0 a N-i para el nodo i'th y seleccionando el nodo si el número generado es igual a 0 o cualquier otro número fijo del 0 al rango N-i.

Este enfoque tiene un revés importante: necesitamos recorrer la lista dos veces. Una vez para contarlo y otra vez para seleccionar un nodo aleatorio. En la mayoría de los casos, no se desea este enfoque, por lo que recurrimos al otro:

  • Muestreo de reservorio - Seleccionamos el primer elemento, independientemente del tamaño de la lista ya que no lo conocemos de antemano. Luego, recorremos la lista hacia adelante considerando todos y cada uno de los nodos posteriores para la selección con la probabilidad 1/n donde n es el número de nodos ya visitados. De esta forma, nos aseguramos de que la probabilidad de elegir cualquier nodo de la lista sea 1/n.

Nota: De hecho, esta es una versión simplificada de Muestreo de yacimientos, que a menudo se usa para seleccionar k elementos de una lista que contiene * n* artículos donde n es desconocido o muy grande. En este caso, también estamos seleccionando k elementos, que resulta ser un solo elemento.

Echemos un vistazo al pseudocódigo detrás de la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
reservoirSample(stream, n, k)
    i = 0
    // initialize reservoir with k elements
    reservoir[k]

    // populate the reservoir with the wanted number of elements
    for i < k
        reservoir[i] = stream[i]

    // iterate from the (k+1)th element to nth element
    while i < n
        // pick random number from 0 to i
        j = randomNumber(i+1)
        // if the random index is smaller than k, replace the element at that index with a new element from te stream
        if j < k
            reservoir[j] = stream[i]

Encontrar el nodo medio

Pregunta de la entrevista {#pregunta de la entrevista}

Número par de elementos

Encuentre el nodo medio en la lista enlazada dada:

1
1->2->3->4->5->6
Número impar de elementos

Encuentre el nodo medio en la lista enlazada dada:

1
1->2->3->4->5

Explicación

Esta pregunta puede tener dos versiones:

  • La lista enlazada tiene un número par de elementos - Estamos buscando los dos elementos del medio ya que no hay un elemento del medio definitivo, después de lo cual seleccionaremos el segundo elemento del medio
  • La lista enlazada tiene un número impar de elementos - Estamos buscando el elemento del medio

Además, también tenemos dos enfoques:

  • Cuente los nodos en la lista, divida el número por 2 y devuelva el nodo en esa posición.
  • Recorre la lista con dos punteros: el primero se incrementa en 1, mientras que el segundo se incrementa en 2. De esta manera, el segundo llegará al final de la lista cuando el primero esté en el medio.

Comencemos con el pseudocódigo detrás del primer enfoque:

1
2
3
4
5
6
7
8
9
int count
Node head

while head is not null
    count+1
    next = head.next
return count

list.getNode(count/2)

Con eso fuera del camino, exploremos el pseudocódigo detrás del segundo enfoque:

1
2
3
4
5
6
Node slow, fast

while(fast is not null && fast.next is not null)
    fast = fast.next.next
    slow = slow.next
return slow

find_middle_node

K-ésimo elemento del último nodo

Pregunta de la entrevista {#pregunta de la entrevista}

Encuentre el quinto elemento desde el final de la lista enlazada:

1
1->2->4->6->7->8->5->9

Explicación

En el caso anterior, estamos buscando el nodo con el valor 6, ya que es el quinto nodo mirando hacia atrás desde el final de la lista.

Hay dos formas de llegar a este nodo:

  • Según la longitud de la lista - (Longitud - n + 1) nodo desde el principio.
  • Uso de punteros - Un puntero de referencia y un puntero principal. Ambos punteros comenzarán al principio de la lista, con el puntero de referencia desplazado por K nodos a lo largo de la lista. Luego, ambos punteros iteran en 1 hasta que el puntero de referencia llega al final. Esto hace que el puntero principal quede detrás del puntero de referencia por el nodo K, apuntando al nodo que estamos buscando.

Veamos el pseudocódigo si confiamos en la longitud de la lista:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
printKthFromLast(int k)
    length = 0
    Node node = head

        // traverse the list and count the elements
        while node is not null
            node = node.next
            length+1
        // if the kth element is larger than the length, return the head
        if length < k
            return
        node = head

        // traverse the list until the element we're searching for and return it
        for i = 0, i < length-k+1, i+1
            node = node.next
        return node

find_kth_based_on_length

Veamos el pseudocódigo si confiamos en los indicadores:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
printKthFromLast(int k)
    Node main = head
    Node reference = head

    // since we're already on the head, the length is equal to 1
    length = 1
    if head is not null
        while length < k
            // checks if we've reached the end
            if reference is null
                return

            reference = reference.next
            length+1
        while reference is not null
            main = main.next
            reference = reference.next
        return main

find_kth_based_on_pointers

Frecuencia de un número dado

Pregunta de la entrevista {#pregunta de la entrevista}

Cuente la cantidad de veces que un número ha aparecido en una lista enlazada determinada:

1
1->2->1->3->1->4->1->5

Explicación

Este es un problema común y simple de encontrar y abordar, y solo se necesitan un par de pasos para encontrar una solución:

  • Declarar un contador
  • Recorre cada elemento de la lista y aumenta el contador cada vez que un elemento es igual al número cuya frecuencia estamos contando
  • Devolver la cuenta

Echemos un vistazo al pseudocódigo detrás de la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
count(searchFor)
    Node curr = head
    count = 0

    while curr is not null
        if curr.data == searchFor
            count++
        curr = curr.next

    return count

Implementar el pseudocódigo en cualquier idioma y ejecutarlo con esta lista produciría:

1
4

Intersección de dos listas enlazadas

Pregunta de la entrevista {#pregunta de la entrevista}

Dadas dos listas enlazadas, donde un nodo en la primera apunta a un nodo en la segunda, en un lugar aleatorio, encuentre el lugar de intersección de estas dos listas.

intersection_of_two_lists

Explicación

Hay varios enfoques que podría tomar aquí:

  • Fuerza bruta: como su nombre lo indica, en forma de fuerza bruta, recorra toda la segunda lista, para cada nodo en la primera lista y verifique la intersección. Este enfoque requiere más tiempo, por lo que es muy ineficiente para usar con listas grandes.
  • Tabla hash: recorre la primera lista y almacena una dirección para cada nodo en un conjunto hash. Luego recorra la segunda lista y si una dirección de la segunda lista ya está almacenada en el conjunto hash, es el nodo de intersección.
  • Dos Punteros - Nuevamente, usando dos punteros, podemos encontrar el nodo de intersección. Inicializa dos punteros, punteroA y punteroB donde ambos punteros recorren la lista paso a paso. Una lista debe ser más pequeña que la otra. Si tuvieran la misma cantidad de nodos y se conectaran al final, sería simplemente una lista enlazada individualmente. Si tienen el mismo número de nodos, la lista que se conecta a la otra lista antes del final se convierte en la lista "más grande" ya que tiene más nodos individuales. Cuando pointerA llegue al final de la lista, rediríjalo al encabezado de la segunda lista. Si en algún punto estos dos punteros se encuentran, ese es el nodo de intersección. Si es un poco confuso, sería mejor echar un vistazo a la animación adjunta a continuación:

intersection_two_pointers

Primero echemos un vistazo al pseudocódigo detrás del enfoque de fuerza bruta:

1
2
3
4
5
6
7
Node list1_curr = head1
Node list2_curr = head2

while list1_curr is not null
    while list2_curr is not null
        if list1_curr == list2_curr
            return list1_curr

Ahora, echemos un vistazo al pseudocódigo detrás del enfoque de tabla hash:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
getIntersectionHashTables(Node head1, Node head2)
    nodes = hashSet

    Node pointerA = head1
    while pointerA is not null
        nodes.add(pointerA)
        pointerA = pointerA.next

    if nodes is empty
        return null

    Node pointerB = head2
    while pointerB is not null
        if nodes contain pointerB
            return pointerB
        pointerB = pointerB.next
    return null

Este también es bastante simple:

  • Tenemos dos cabezas para cada lista enlazada.
  • Agregamos todos los nodos de la primera lista en un conjunto hash y luego recorremos la segunda lista, verificando si la tabla hash ya contiene dicho nodo.
  • Si la tabla hash contiene el nodo, se devuelve y si no, se devuelve null.

Finalmente, echemos un vistazo al enfoque de dos indicadores:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
if pointerA is null and pointerB is null
    return null

while pointerA is not pointerB
    pointerA = pointerA.next
    pointerB = pointerB.next

    if pointerA is null
        pointerA = headB
    if pointerB is null
        pointerB = headA

return pointerA

Recursos

Si estás buscando una mejor manera de practicar este tipo de preguntas de entrevistas de programación, así como otras, te recomendamos que pruebes un servicio como [Problema de codificación diaria](https://stackabu.se/ problema de codificación diaria). Le enviarán un nuevo problema para resolver todos los días, todos los cuales provienen de las mejores empresas. También puedes saber más aquí si quieres más info.

Conclusión

En este artículo, hemos cubierto las preguntas comunes de la entrevista relacionadas con las listas vinculadas.

Nuevamente, si está interesado en leer más sobre Preguntas de la entrevista de programación en general, hemos compilado una larga lista de estas preguntas, incluyendo sus explicaciones, implementaciones, representaciones visuales y aplicaciones.