Dada una lista enlazada simple y dos enteros left y right donde left <= right, el objetivo es invertir los nodos de la lista desde la posición left hasta la posición right y devolver la cabeza de la lista modificada.

Estrategia 1: Delimitación de Segmentos y Reversión

Esta técnica consiste en localizar los nodos límite del segmento a invertir, aislar dicha sublista, revertirla y finalmente reconectarla con el resto de la estructura principal.

Pasos detallados:

1. Inicialiazr un nodo ficticio (dummy) para manejar casos extremos donde la inversión comienza en la cabeza de la lista.
2. Desplazar un puntero prevStart hasta el nodo inmediatamente anterior a la posición left.
3. Identificar startNode (posición left) y endNode (posición right), así como nextEnd (nodo posterior a right).
4. Desconectar el segmento y aplicar una función de inversión sobre el mismo.
5. Reconectar los punteros: prevStart apunta a la nueva cabeza del segmento invertido, y la cola del segmento invertido apunta a nextEnd.

class LinkedListReverser {
    public ListNode invertSegment(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prevStart = dummy;

        for (int i = 1; i < left; i++) {
            prevStart = prevStart.next;
        }

        ListNode startNode = prevStart.next;
        ListNode endNode = startNode;
        for (int i = 0; i < right - left; i++) {
            endNode = endNode.next;
        }

        ListNode nextEnd = endNode.next;
        endNode.next = null; // Desconectar el segmento

        prevStart.next = reverseList(startNode);
        startNode.next = nextEnd;

        return dummy.next;
    }

    private ListNode reverseList(ListNode node) {
        ListNode prev = null;
        ListNode curr = node;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

Estrategia 2: Inserción Sucesiva en la Cabeza del Segmento

Este método optimiza el proceso realizando la inversión en un solo recorrido. En lugar de aislar la sublista, mueve iterativamente cada nodo del segmento objetivo hacia la posición inicial del mismo (justo después del predecesor).

Pasos detallados:

1. Configurar un nodo ficticio y ubicar el puntero boundaryPrev en la posición left - 1.
2. El puntero current se sitúa en la posición left.
3. En cada iteración, se extrae el nodo siguiente a current y se inserta inmediatametne después de boundaryPrev.
4. Este proceso se repite right - left veces, reorganizando los enlaces in-place sin necesidad de realizar un segundo recorrido para la reconexión.

class LinkedListReverserOptimized {
    public ListNode invertSegmentInPlace(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode boundaryPrev = dummy;

        for (int i = 0; i < left - 1; i++) {
            boundaryPrev = boundaryPrev.next;
        }

        ListNode current = boundaryPrev.next;

        for (int i = 0; i < right - left; i++) {
            ListNode nextNode = current.next;
            
            // Reasignación de punteros para mover nextNode al frente del segmento
            current.next = nextNode.next;
            nextNode.next = boundaryPrev.next;
            boundaryPrev.next = nextNode;
        }

        return dummy.next;
    }
}