Inversion d'une liste singulièrement liée lorsqu'une taille de bloc est donnée

Question

Il s'agit d'une liste chaînée à connexion unique et la taille du bloc est donnée. 1->2->3->4->5->6->7->8-NULL et la taille de mon bloc est 4 puis inverser le premier 4 Le résultat de ce problème devrait être le suivant 4->3->2->1->8->7->6->5-NULL

J'ai pensé à diviser la liste liée en segments de taille 4 et ensuite l'inverser. Mais de cette façon, je suis obligé d'utiliser beaucoup de nœuds supplémentaires, ce qui n'est pas du tout souhaité. La complexité de l'espace doit être réduite au minimum.

Il serait très appréciable que quelqu'un puisse proposer une meilleure solution permettant de réduire au minimum l'utilisation de nœuds supplémentaires.

Answer 1

J'ai essayé ceci... ça semble fonctionner correctement...

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

Vous pouvez avancer en échangeant l'élément actuel avec le suivant 3 fois : 1234, 2134, 2314, 2341. Ensuite, faites-le deux fois pour obtenir 3421. Puis une fois pour obtenir 4321. Avancez ensuite de 4 pas et répétez le processus avec le bloc suivant.

Answer 3

Cela peut être fait en temps linéaire, avec un espace constant. Voici une brève description :

1. Diviser la liste chaînée en deux parties par taille de bloc.

   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. Inverser les deux sous-parties, (utiliser une fonction non récursive à temps linéaire et à espace constant).

   reverse(listA);
   reverse(listB);

3. Reliez-les pour obtenir la liste liée souhaitée.

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