6-9 Inversión por segmentos de lista enlazada simple (25 puntos)

Dado una lista enlazada simple con nodo cabecera y un antero K, debes invertir cada grupo de K nodos en la lista. Por ejemplo, dada la lista 1→2→3→4→5→6 y K=3, necesitas transformarla a 3→2→1→6→5→4; si K=4, deberías obtener 4→3→2→1→5→6.

Definición de la interfaz:

void segmentInvert(List L, int K);

Donde la estructura List se define como:

typedef struct Node *PointerNode;
struct Node {
    DataType Data; /* Almacena los datos del nodo */
    PointerNode Next; /* Puntero al siguiente nodo */
};
typedef PointerNode List; /* Define el tipo de lista enlazada simple */

L es la lista enlazada simple con nodo cabecrea, K es la longitud de cada segmanto. La función segmentInvert debe invertir los nodos en L según los requisitos por segmentos.

Ejemplo de programa de prueba:

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct Node *PointerNode;
struct Node {
    DataType Data; /* Almacena los datos del nodo */
    PointerNode Next; /* Puntero al siguiente nodo */
};
typedef PointerNode List; /* Define el tipo de lista enlazada simple */

List readInput(); /* Implementado por el juez, detalles omitidos */
void printList(List L); /* Implementado por el juez, detalles omitidos */
void segmentInvert(List L, int K);

int main()
{
    List L;
    int K;

    L = readInput();
    scanf("%d", &K);
    segmentInvert(L, K);
    printList(L);

    return 0;
}

/* Tu código será insertado aquí */

Caso de entrada:

6
1 2 3 4 5 6
4

Caso de salida:

4 3 2 1 5 6

void segmentInvert(List L, int K){
    PointerNode cursor, nextNode, connector1, connector2, head = L->Next;
    
    /* connector1 y connector2 se utilizan para conectar segmentos invertidos;
       inicialmente establecemos connector1 apuntando al nodo cabecera, 
       connector2 apuntando al nodo con valor 1, ¿por qué?
       porque los primeros cuatro elementos deben insertarse mediante inserción
       por cabeza detrás de L, es decir, detrás de connector1;
       cuando llegamos al nodo 5, debemos hacer connector1 = connector2; connector2 = nodo 5;
       luego debemos insertar 5 6 7 8 mediante inserción por cabeza detrás del nodo 1,
       es decir, detrás de connector1
       significa que siempre insertamos nodos mediante inserción por cabeza detrás de connector1,
       mientras connector2 registra el primer nodo del siguiente segmento,
       es decir, el próximo connector1, actualizando continuamente connector1
       podemos lograr la inversión por segmentos de toda la lista;
       esta es la función de connector1 y connector2
    */
    connector1 = L;
    connector2 = L->Next;
    cursor = L->Next;
    nextNode = cursor->Next;
    int totalNodes = 0;
    
    /*
        totalNodes registra el número total de nodos;
        ¿Por qué registrar el total?
        porque necesitamos saber si el último segmento tiene menos de K nodos o exactamente K;
        si tiene menos, no se invierte, si es exactamente K, también se invierte ese segmento;
    */
    if (K >= 1) {
        // contar total
        while (head) {
            totalNodes++;
            head = head->Next;
        }
        
        // verificar, si total < K no cambiar la lista
        if (totalNodes >= K) {
            /* totalNodes/K es cuántos segmentos necesitamos recorrer, como el resultado de totalNodes/K es cociente,
               entonces si totalNodes no es divisible por K, es decir, el último segmento tiene menos de K, no lo recorremos
               es decir, no lo tocamos.
            */
            for (int segment = 0; segment < totalNodes / K; segment++) {
                // cada segmento recorre K veces
                for(int pos = 0; pos < K; pos++) {
                    cursor->Next = connector1->Next; // inserción por cabeza
                    connector1->Next = cursor;
                    cursor = nextNode;
                    /*
                     ¿Por qué verificar si nextNode no es nulo?
                     porque inicialmente establecí: cursor = L->Next;
                                     nextNode = cursor->Next;
                     así que finalmente nextNode apunta al campo Next del último nodo de la lista, que es nulo,
                     por lo tanto no existe nextNode->Next, si no verificamos, el programa no seguirá ejecutándose
                     pero durante la compilación inicial no dará error, por lo tanto este punto es muy importante,
                     es decir, verificar problemas de límites, encontré este punto después de buscar por mucho tiempo.
                    */
                    if(nextNode)
                        nextNode = nextNode->Next;
                }
                connector1 = connector2; // actualizar connector1 y connector2
                connector2 = cursor;
            }
            connector1->Next = cursor; // finalmente establecer el campo Next del nodo final como nulo.
        }
    }
}