algorithm - nodos - Invertir una lista vinculada individualmente cuando se da un tamaño de bloque

listas simples estructura de datos

Question

Hay una lista enlazada conectada solo y se da un tamaño de bloque. Por ejemplo, si mi lista vinculada es 1->2->3->4->5->6->7->8-NULL y mi tamaño de bloque es 4 luego invierta los primeros 4 elementos y luego los segundos 4 elementos. La salida del problema debe ser 4->3->2->1->8->7->6->5-NULL

Estaba pensando en dividir la lista enlazada en segmentos de tamaño 4 y luego invertirla. Pero de esa manera me veo obligado a usar muchos nodos adicionales que no se desean en absoluto. La complejidad del espacio debe mantenerse al mínimo.

Será muy apreciable si alguien puede venir con una mejor solución donde el uso de nodos adicionales se mantendría al mínimo.

Answer 1

Intenté esto ... parece funcionar bien ...

node* reverse(node* head) // function to reverse a list
{
    node* new_head = NULL;
    while(head != NULL)
    {
        node* next = head->next;
        head->next = new_head;
        new_head = head;
        head = next;
    }
    return new_head;
}

node* reverse_by_block(node* head, int block)
{
    if(head == NULL)
            return head;

    node* tmp = head;
    node* new_head = head;
    node* new_tail = NULL;

    int count = block;
    while(tmp != NULL && count--)
    {
        new_tail = tmp;
        tmp = tmp->next;
    }

    new_tail->next = NULL;
    new_tail = new_head;
    new_head = reverse(new_head);
    new_tail->next = reverse_by_block(tmp,block);

    return new_head;
}

Answer 2

Puede avanzar intercambiando el elemento actual con las siguientes 3 veces: 1234, 2134, 2314, 2341. Luego, hágalo dos veces para obtener 3421. Luego, una vez para obtener 4321. Luego avance 4 pasos y repita el proceso con el bloque siguiente.

Answer 3

Esto se puede hacer en tiempo lineal, con espacio constante. Aquí hay una breve descripción:

1. Divida la lista enlazada en dos partes por tamaño de bloque

   int split(node* head, node** listA, node** listB size_t block_size)
   {
   node* cur = head;
   
   while(block_size && cur)
   {
      cur = cur->next;
      --block_size;
   }
   if(!cur) { /* error : invalid block size */ return -1; }
   *listA = head;
   *listB = cur->next;
   cur->next = NULL; /* terminate list A */
   return 0;
   }

2. Invierta las dos subpartes, (use una función de tiempo constante no recursivo, espacio constante)

   reverse(listA);
   reverse(listB);

3. Enlácelos para obtener la lista vinculada deseada.

   cur = *listA;
   /* goto last but one element of listA */
   while(cur->next) cur = cur->next; 
   cur->next = *listB;