Combinar, dividir y encontrar el enésimo elemento desde el final
Combine dos listas enlazadas ordenadas en O(n), divida una lista por el punto medio usando punteros lento y rápido, y encuentre el enésimo nodo desde la cola.
Combinar, dividir y encontrar el enésimo elemento desde el final es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Tres patrones esenciales de listas enlazadas
Esta lección cubre tres operaciones fundamentales de listas enlazadas que aparecen constantemente como bloques de construcción en problemas más difíciles: fusionar dos listas ordenadas (utilizado en merge sort y K-way merge), dividir una lista por su punto medio (utilizado en merge sort y la detección de palíndromos) y encontrar el nodo n desde el final (utilizado en remove-nth-from-end).
Las tres se basan en técnicas que ya ha visto: el nodo de cabeza ficticia, los punteros lento y rápido y un seguimiento cuidadoso de los límites.
Fusionar dos listas ordenadas
LeetCode 21 'Merge Two Sorted Lists': dadas dos listas enlazadas ordenadas, devuelva una única lista ordenada fusionada. Utilice una cabeza ficticia y un puntero de cola curr. En cada paso, compare las cabezas de las dos listas y conecte el nodo menor a curr. Cuando una lista se agote, conecte el resto de la otra. Tiempo: O(n+m); espacio: O(1) (reconexión in situ).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))Trazar la fusión paso a paso
Siga el trazado de mergeTwoLists([1,2,4], [1,3,4]): compare 1 y 1; elija l1(1) y avance l1 hasta 2. Compare 2 y 1; elija l2(1) y avance l2 hasta 3. Compare 2 y 3; elija l1(2) y avance l1 hasta 4. Compare 4 y 3; elija l2(3) y avance l2 hasta 4. Compare 4 y 4; elija l1(4) y avance l1 hasta None. Conecte el l2(4) restante. Resultado: [1,1,2,3,4,4].
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))Encontrar el punto medio con punteros lento y rápido
Para dividir una lista por su punto medio, utilice el patrón de punteros lento y rápido. slow avanza 1 paso y fast avanza 2 pasos. Cuando fast llega a None (o al último nodo), slow se encuentra en el punto medio. En una lista de longitud par, esto produce el primero de los dos nodos centrales, que es lo convencional para dividir una lista mediante merge sort.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]Merge sort en una lista enlazada
LeetCode 148 'Ordenar lista': ordene una lista enlazada en tiempo O(n log n) y con espacio O(log n). El enfoque consiste en dividir la lista por el punto medio, ordenar cada mitad de forma recursiva y fusionarlas. El merge sort de listas enlazadas resulta natural porque dividir por el punto medio cuesta O(n) (no O(1) como en los arrays), pero la complejidad total sigue siendo O(n log n), con solo O(log n) de espacio en la pila.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]Encontrar el n-ésimo nodo desde el final
LeetCode 19 'Eliminar el n-ésimo nodo desde el final de la lista': encuentre el n-ésimo nodo desde el final en un solo recorrido. Use dos punteros separados exactamente por n nodos. Avance fast n pasos por delante de slow. Después, avance ambos a la vez hasta que fast llegue al último nodo. En ese momento, slow se encuentra en el nodo (n+1)-ésimo desde el final: el predecesor del nodo que se debe eliminar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]Por qué se dan n+1 pasos al eliminar el n-ésimo nodo
La sutileza clave consiste en avanzar n+1 pasos (no n) desde la cabeza ficticia. Después de n+1 pasos, fast está n+1 posiciones por delante de slow (ambos comienzan en la cabeza ficticia). Cuando fast llega a None (una posición después del final), slow se encuentra n+1 posiciones antes de None; es decir, está en la posición (longitud - n - 1), contando desde cero, o en el predecesor del objetivo. Esto permite que slow.next = slow.next.next elimine limpiamente el n-ésimo nodo desde el final.
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')Intersección de dos listas enlazadas
LeetCode 160 'Intersección de dos listas enlazadas': encuentre el nodo en el que dos listas se intersectan por primera vez. El truco de espacio O(1) consiste en avanzar dos punteros, uno por lista. Cuando un puntero llega a None, rediríjalo a la cabeza de la otra lista. Después de como máximo len(A) + len(B) pasos, ambos punteros habrán recorrido la misma distancia total y necesariamente estarán en el nodo de intersección (o ambos en None si no hay intersección).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8Fusionar k listas ordenadas (divide y vencerás)
LeetCode 23 'Fusionar k listas ordenadas': dadas k listas ordenadas, fusiónelas en una sola. El enfoque óptimo consiste en fusionar repetidamente pares de listas mediante divide y vencerás, reduciendo a la mitad el número de listas en cada ronda. Con k listas de longitud media n, esto requiere un tiempo O(n k log k), frente a O(n k²) si se fusionan secuencialmente. Un enfoque con min-heap también tiene una complejidad O(n k log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]Lista enlazada de índices impares y pares
LeetCode 328 'Lista enlazada de índices impares y pares': agrupe primero todos los nodos de índices impares y después los de índices pares (con indexación desde 1). El enfoque consiste en mantener dos cadenas separadas (impares y pares) y conectarlas al terminar. Basta con recorrer la lista una vez, lo que proporciona un tiempo O(n) y un espacio O(1). Es un ejemplo claro de cómo avanzar simultáneamente dos punteros con pasos diferentes.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]Integración de todos los conceptos
Los tres patrones de esta lección —fusionar listas ordenadas, dividir por el punto medio y encontrar el n-ésimo nodo desde el final— comparten un tema: usar variables adicionales de tipo puntero para controlar posiciones sin memoria adicional. La cabeza ficticia simplifica la fusión y la eliminación; la separación entre los punteros lento y rápido fija una posición relativa concreta; avanzar primero un puntero crea la separación deseada.
En una entrevista, indique el patrón que va a usar antes de escribir código: 'Usaré la técnica de separación entre dos punteros para encontrar el n-ésimo nodo desde el final en un solo recorrido'. Esto demuestra un razonamiento estructurado.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que fusionar dos listas ordenadas utiliza una cabeza ficticia y una comparación en cada paso, con O(n+m) de tiempo y O(1) de espacio, que dividir por el punto medio utiliza punteros lento y rápido, y fast se detiene en el último par válido, y que para encontrar el n-ésimo nodo desde el final se avanza fast n+1 pasos para que slow quede en el predecesor. A continuación, crearemos pilas y colas y las aplicaremos a problemas clásicos de entrevistas.
Preguntas frecuentes
¿La lección «Combinar, dividir y encontrar el enésimo elemento desde el final» es gratis?
Sí — el texto completo de «Combinar, dividir y encontrar el enésimo elemento desde el final» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Combinar, dividir y encontrar el enésimo elemento desde el final»?
Combine dos listas enlazadas ordenadas en O(n), divida una lista por el punto medio usando punteros lento y rápido, y encuentre el enésimo nodo desde la cola. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Combinar, dividir y encontrar el enésimo elemento desde el final»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Clase Node y construcción de listas
- Inversión de una lista enlazada
- Detección de ciclos con el algoritmo de Floyd
- Combinar, dividir y encontrar el enésimo elemento desde el final