La técnica de dos punteros es una de las optimizaciones más eficaces para resolver problemas de búsqueda y manipulación de secuencias. Se divide principalmente en dos enfoques: punteros convergentes (o de colisión) y punteros de velocidad relativa (rápido y lento).

Punteros Convergentes: Búsqueda en Arreglos Ordenados

Considerando un arreglo de enteros previamente ordenado y un valor objetivo (target), el reto consiste en encontrar los índices de dos elementos cuya suma coincida exactamente con dicho objetivo. Mientras que una búsqueda por fuerza bruta requeriría un tiempo de O(n²), el uso de punteros en los extremos permite reducir la complejidad temporal a O(n).

Aprovechando que el arreglo está ordenado, si la suma actual es menor que el objteivo, incrementamos el puntero izquierdo para aumentar el valor. Si es mayor, decrementamos el puntero derecho para reducirlo.

#include <iostream>
#include <vector>

struct Resultado {
    int idxA;
    int idxB;
};

Resultado encontrarParSuma(const std::vector<int>& numeros, int meta) {
    int inicio = 0;
    int fin = numeros.size() - 1;

    while (inicio < fin) {
        int sumaActual = numeros[inicio] + numeros[fin];

        if (sumaActual == meta) {
            return {inicio + 1, fin + 1}; // Retorna índices basados en 1
        } else if (sumaActual < meta) {
            inicio++;
        } else {
            fin--;
        }
    }
    return {-1, -1};
}

int main() {
    std::vector<int> datos = {2, 7, 11, 15};
    int objetivo = 9;
    Resultado res = encontrarParSuma(datos, objetivo);
    std::cout << "Índices: " << res.idxA << ", " << res.idxB << std::endl;
    return 0;
}

Aplicaciones Adicionales de Colisión

Este mismo principio de punteros que se acercan desde los extremos es fundamental para resolver:

• Validación de Palíndromos: Comparar caracteres desde fuera hacia dentro ignorando caracteres no alfanuméricos.
• Inversión de Cadenas: Intercambiar el elemento en el índice inicial con el final y avanzar hacia el centro.
• Inversión Selectiva: Por ejemplo, invertir únicamente las vocales dentro de una cadena manteniendo el resto de las consonantes en su sitio.

Punteros Rápidos y Lentos (Algoritmo de Floyd)

Esta variante se utiliza frecuentemente en listas enlazadas para detectar ciclos. La lógica se basa en que si dos punteros recorren un circuito a diferentes velocidades, eventualmente se encontrarán si existe un bucle.

Para identificar el nodo exacto donde comienza el ciclo, una vez que los punteros se encuentran, se reinicia un puntero al inicio de la lista y se avanza ambos a la misma velocidad. El punto de nuevo encuentro será la entrada del ciclo.

struct Nodo {
    int valor;
    Nodo* siguiente;
};

Nodo* detectarEntradaCiclo(Nodo* cabeza) {
    if (!cabeza || !cabeza->siguiente) return nullptr;

    Nodo* lento = cabeza;
    Nodo* rapido = cabeza;
    bool existeCiclo = false;

    // Fase 1: Detectar presencia de ciclo
    while (rapido != nullptr && rapido->siguiente != nullptr) {
        lento = lento->siguiente;
        rapido = rapido->siguiente->siguiente;

        if (lento == rapido) {
            existeCiclo = true;
            break;
        }
    }

    if (!existeCiclo) return nullptr;

    // Fase 2: Localizar el inicio del ciclo
    Nodo* aux = cabeza;
    while (aux != lento) {
        aux = aux->siguiente;
        lento = lento->siguiente;
    }

    return aux;
}

Este enfoque optimiza el uso de memoria, logrando una complejidad espacial de O(1), a diferencia de las tablas de hash que requieren O(n) para almacenar los nodos visitados.