Reverse Nodes in k-Group

Q: ¿Cuál es la complejidad temporal y espacial de invertir nodos en grupos de k?

Se ejecuta en tiempo O(L) para una lista de L nodos: cada nodo se cuenta una vez y se invierte una vez. La versión que opera in situ usa O(1) de memoria adicional; copiar los valores en un arreglo usa O(L).

Q: ¿Qué ocurre con el último grupo si tiene menos de k nodos?

Mantiene su orden original. Cuenta los nodos k antes de invertir cada grupo; si llegas primero al final de la lista, deja el resto tal como está.

DifícilLista enlazada

+10

Una lista enlazada simple se almacena en dos arreglos de la misma longitud. El nodo i contiene values[i] y enlaza con el nodo next[i]; -1 indica el final de la lista, y la cabeza es el nodo 0. Los nodos pueden estar almacenados en cualquier orden, así que sigue los enlaces, no el orden del arreglo.

Invierte la lista en grupos de k nodos: los primeros k nodos quedan invertidos, después los siguientes k, y así sucesivamente. Un último grupo con menos de k nodos conserva su orden. Devuelve los valores en el nuevo orden de la lista.

Función

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array

nextinteger-array: el índice del nodo al que enlaza cada nodo, o -1 para el último nodo
valuesinteger-array: el valor que contiene cada nodo
kinteger: el número de nodos que se invertirán en cada grupo
Devuelveinteger-array: los valores en el orden de la nueva lista

Restricciones

1 ≤ L ≤ 5000, donde L es la longitud de next y de values.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Cada next[i] es -1 o un índice de nodo de 0 a L-1.
Empezando en el nodo 0, la lista visita cada nodo exactamente una vez y después llega a -1. No hay ningún ciclo.

Ejemplos

Entrada: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Salida: [2, 1, 4, 3, 5]
Explicación: La lista se lee 1, 2, 3, 4, 5 (nodos 0, 2, 4, 1, 3). Los pares 1, 2 y 3, 4 están invertidos, y 5 por sí solo es más corto que k = 2, así que se queda al final.

Entrada: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Salida: [30, 20, 10, 60, 50, 40, 70, 80]
Explicación: La lista se lee 10, 20, ..., 80. Los grupos 10, 20, 30 y 40, 50, 60 están invertidos. 70, 80 es más corto que k = 3, así que conserva su orden.

Entrada: next = [2, -1, 1]values = [7, 9, 3]k = 3
Salida: [9, 3, 7]
Explicación: El arreglo se lee 7, 9, 3, pero la lista se lee 7, 3, 9. Con k igual a la longitud, toda la lista forma un grupo y queda invertida: 9, 3, 7.

Para ir más allá

¿Puedes escribirlo de forma recursiva, invirtiendo un grupo y recurriendo sobre el resto de la lista? ¿Cuánta memoria adicional utiliza?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Invertir una lista completa consiste en una pasada de cambios de enlaces. Aquí, los cambios se detienen cada k nodos, y cada grupo invertido debe enlazarse con la parte anterior y los nodos posteriores. Puedes copiar los valores en un arreglo e invertir bloques, o volver a enlazar cada grupo en su lugar con memoria extra O(1).

Copia los valores e invierte cada bloque

Intuición

Recorre la lista desde el nodo 0 con node = next[node] y copia los valores en un arreglo en el orden de la lista. Los grupos son ahora los bloques de índices 0 a k-1, k a 2k-1, y así sucesivamente: invierte cada bloque que quepa entero y deja sin cambios el último bloque, si es más corto. Esto toma un tiempo O(L) y memoria adicional O(L), y nunca modifica ningún enlace.

Algoritmo

Avanza desde el nodo 0 hasta -1 y agrega values[node] a un arreglo.
Para start = 0, k, 2k, ..., mientras start + k ≤ L: invierte el bloque desde el índice start hasta start+k-1.
Deja sin cambios un bloque más corto al final.
Devuelve el arreglo.

def reverseKGroup(next, values, k):
    # Read the values in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Reverse every full block of k; a shorter last block stays as it is.
    for start in range(0, len(order) - k + 1, k):
        order[start:start + k] = order[start:start + k][::-1]
    return order

Invierte cada grupo en su lugar reenlazando

Intuición

Para invertir una lista completa, la recorres con prev y node y estableces next[node] = prev. Un grupo es el mismo bucle ejecutado k veces, con prev empezando en after, el nodo justo después del grupo. El primer nodo del grupo pasa a ser el último y apunta a after, así que el resto de la lista permanece unido.

Cuenta k nodos antes de invertirlos: si llegas primero a -1, el resto es un grupo corto y se queda como está. Después de invertirlo, prev es el nuevo primer nodo del grupo. Conéctalo con el último nodo del grupo anterior o conviértelo en la cabeza si es el primer grupo. El antiguo primer nodo del grupo ahora es el último nodo de la parte procesada.

Cada nodo se visita dos veces, una para contar y otra para invertir: tiempo O(L) y unos pocos enteros de memoria (O(L) en R, que copia el vector de enlaces en su primer cambio).

Algoritmo

Empieza con head = 0, prevTail = -1, groupStart = 0.
Avanza k pasos desde groupStart hasta after; si llegas primero a -1, ve al paso 5.
Con prev = after y node = groupStart, repite k veces: guarda next[node], establece next[node] = prev y avanza ambos.
Si prevTail es -1, establece head = prev; si no, establece next[prevTail] = prev. Establece prevTail = groupStart, groupStart = after; ve al paso 2.
Recopila los valores desde head.

def reverseKGroup(next, values, k):
    head = 0           # the list's head; changes after the first group
    prev_tail = -1     # last node of the groups already reversed
    group_start = 0
    while True:
        # Find the node right after this group, or stop if fewer than k remain.
        after, count = group_start, 0
        while after != -1 and count < k:
            after = next[after]
            count += 1
        if count < k:
            break
        # Turn the group's k links around. Its first node ends up last
        # and links to the node after the group.
        prev, node = after, group_start
        for _ in range(k):
            following = next[node]
            next[node] = prev
            prev, node = node, following
        # prev is the group's new first node: hang it after the previous group.
        if prev_tail == -1:
            head = prev
        else:
            next[prev_tail] = prev
        prev_tail = group_start
        group_start = after
    # Walk the relinked list from its head.
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Errores comunes y casos límite

Invertir el último grupo corto. Cuenta k nodos antes de invertirlos; no se puede deshacer un enlace invertido sin otra pasada.
Iniciar la inversión con prev = -1, como en una inversión completa. Entonces, una cola corta se desprende: el primer ejemplo devuelve 2, 1, 4, 3.
No enlazar el último nodo del grupo anterior con el nuevo primer nodo. Sigue apuntando al antiguo primer nodo, por lo que desaparecen k-1 nodos.
Leer la respuesta desde el nodo 0 o leer values de izquierda a derecha. Una vez que se invierte un grupo de k ≥ 2, el nodo 0 no es la cabeza, y el orden del arreglo nunca fue el orden de la lista.
Usar índices desde 0 en Lua y R, cuyos arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 y lee next[node + 1].

Preguntas frecuentes3

¿Cuál es la complejidad temporal y espacial de invertir nodos en grupos de k?

Se ejecuta en tiempo O(L) para una lista de L nodos: cada nodo se cuenta una vez y se invierte una vez. La versión que opera in situ usa O(1) de memoria adicional; copiar los valores en un arreglo usa O(L).

¿Qué ocurre con el último grupo si tiene menos de k nodos?

Mantiene su orden original. Cuenta los nodos k antes de invertir cada grupo; si llegas primero al final de la lista, deja el resto tal como está.

¿Por qué las soluciones a este problema usan un nodo ficticio?

Con los objetos nodo, un nodo ficticio antes de la cabeza le da al primer grupo un nodo delante, de modo que una línea conecta cada grupo con la parte terminada. Con un arreglo de enlaces, un prevTail que permanece en -1 hasta que el primer grupo está listo cumple la misma función.

def reverseKGroup(next, values, k):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

Salida Esperada

[2, 1, 4, 3, 5]