Fusión de dos listas enlazadas ordenadas (LeetCode 21)

Este problema se puede resolver de manera iterativa utilizando un nodo centinela para simplificar la construcción de la lista resultante. La idea consiste en recorerr ambas listas simultáneamente, comparando los valores de los nodos actuales y enlazando el menor al resultado.

Se define un nodo centinela que sirve como punto de partida, y un puntero que avanza conforme se van añadiendo nodos. Cuando una de las listas se agota, se conecta directamente el resto de la otra lista.

Complejidad temporal: O(m + n), donde m y n son las longitudes de las listas.

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var mergeTwoLists = function(headA, headB) {
    const sentinel = new ListNode(-1);
    let cursor = sentinel;

    while (headA !== null && headB !== null) {
        if (headA.val <= headB.val) {
            cursor.next = headA;
            headA = headA.next;
        } else {
            cursor.next = headB;
            headB = headB.next;
        }
        cursor = cursor.next;
    }
    cursor.next = headA !== null ? headA : headB;
    return sentinel.next;
};

Fusión de K listas enlazadas ordenadas (LeetCode 23)

Enfoque 1: Cola de prioridad

Una cola de prioridad (Priority Queue) es una estructura de datos que permite obtener eficientemente el elemento con mayor prioridad y agregar nuevos elementos. Internamente suele implementarse mediante un heap binario, que es un árbol binario completo con propiedades de ordenamiento.

Para este problema, se inserta el primer nodo de cada lista en la cola de prioridad, ordenados por su valor. Luego, se extrae repetidamente el nodo con menor valor, se añade al resultado, y se inserta el siguiente nodo de la misma lista si existe.

Complejidad temporal: O(n log k), donde n es el total de elemantos y k es el número de listas.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<listnode> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val)
        );

        ListNode sentinel = new ListNode(0);
        ListNode tail = sentinel;

        for (ListNode node : lists) {
            if (node != null) heap.offer(node);
        }

        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();
            tail.next = smallest;
            tail = tail.next;
            if (smallest.next != null) heap.offer(smallest.next);
        }

        return sentinel.next;
    }
}</listnode>

Enfoque 2: Fusión ascendente por pares

En lugar de usar una cola de prioridad, se pueden fusionar las listas de dos en dos de forma iterativa, similar al merge sort ascendente. Se comienza con un intervalo de 1, fusionando listas adyacentes, y se va duplicando el intervalo hasta que solo queda una lista.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        int gap = 1;
        while (gap < lists.length) {
            for (int i = 0; i + gap < lists.length; i += gap * 2) {
                lists[i] = mergePair(lists[i], lists[i + gap]);
            }
            gap *= 2;
        }
        return lists[0];
    }

    private ListNode mergePair(ListNode a, ListNode b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.val < b.val) {
            a.next = mergePair(a.next, b);
            return a;
        }
        b.next = mergePair(a, b.next);
        return b;
    }
}

Inversión de nodos en grupos de K (LeetCode 25)

Este problema se aborda de forma iterativa. Se utiliza un nodo centinela y un puntero al grupo anterior. Para cada grupo, se localiza el nodo final tras recorrer k posiciones. Si no hay suficientes nodos, se termina. En caso contrario, se invierte el rango del grupo, se reconecta con el grupo anterior y se avanza.

La inversión del rango se realiza mediante un método auxiliar que invierte los enlaces entre dos nodos dados.

Complejidad temporal: O(n). Complejidad espacial: O(1).

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;

        ListNode guard = new ListNode(0);
        guard.next = head;
        ListNode prevGroup = guard;

        while (head != null) {
            ListNode groupEnd = head;
            int cnt = 1;
            while (cnt < k && groupEnd != null) {
                groupEnd = groupEnd.next;
                cnt++;
            }
            if (groupEnd == null) break;

            ListNode nextStart = groupEnd.next;
            ListNode newHead = reverseRange(head, groupEnd);

            prevGroup.next = newHead;
            head.next = nextStart;

            prevGroup = head;
            head = nextStart;
        }

        return guard.next;
    }

    private ListNode reverseRange(ListNode start, ListNode end) {
        ListNode prev = null;
        ListNode curr = start;
        ListNode boundary = end.next;
        while (curr != boundary) {
            ListNode tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }
        return prev;
    }
}

Subarray con suma máxima (LeetCode 53)

Se utiliza el algoritmo de Kadane, que mantiene una suma acumulada del subarray actual. Si en algún momento la suma acumulada se vuelve negativa, se descarta y se reinicia desde el siguiente elemento, ya que un prefijo negativo nunca contribuye positivamente a un subarray futuro.

En cada iteración, se compara la suma actual con el mejor valor encotnrado hasta el momento y se actualiza si es mayor.

Complejidad temporal: O(n). Complejidad espacial: O(1).

int maxSubArray(int* nums, int numsSize) {
    int best = nums[0];
    int running = nums[0];

    for (int i = 1; i < numsSize; i++) {
        if (running < 0) {
            running = nums[i];
        } else {
            running += nums[i];
        }
        if (running > best) {
            best = running;
        }
    }

    return best;
}