реверсивный связанный список

Question

Я пытаюсь перевернуть связанный список с помощью рекурсии и написал следующий код для него.Список является началом списка в начале.

 node *reverse_list_recursive(node *list)
 {
      node *parent = list;
      node *current = list->next;

      if(current == NULL)
       return parent;

      else
       {
           current = reverse_list_recursive(current);
           current->next = parent;
           printf("\n %d  %d \n",current->value,parent->value);
           return parent;
       }

  }

Я мог видеть, что все ссылки становятся обратными.Однако, когда я пытаюсь отобразить, я получаю бесконечные отпечатки чисел.Я подозреваю ошибку, когда пытаюсь изменить ссылку на первый номер в списке.

Что я делаю не так?

Answer 1

Предположим, у меня есть связанный список:

 ----------      ----------      ----------      ---------- 
|  1  |    |--->|  2  |    |--->|  3  |    |--->|  4  |    |--->NULL
 ----------      ----------      ----------      ---------- 

Ваш код преобразует его в:

   ----------------------          ----------------------
   |                    |          |                    |
   v                    |          v                    |
 ----------      ----------      ----------      ----------
|  1  |    |--->|  2  |    |    |  3  |    |    |  4  |    | 
 ----------      ----------      ----------      ---------- 
                   ^                    |
                   |                    |
                   ----------------------

Обратите внимание, что первый элемент по-прежнему указывает на 2.

Если вы добавите строку parent->next = NULL после первых двух, вы получите:

           ----------------------          ----------------------
           |                    |          |                    |
           v                    |          v                    |
         ----------      ----------      ----------      ----------
NULL<---|  1  |    |    |  2  |    |    |  3  |    |    |  4  |    | 
         ----------      ----------      ----------      ---------- 
                           ^                    |
                           |                    |
                           ----------------------

что на самом деле является правильной структурой.

Полный код: (Вам нужно только напечатать текущее значение для каждого рекурсивного вызова)

node *reverse_list_recursive(node *list)
  {
      node *parent = list;
      node *current = list->next;

      if(current == NULL)
       return parent;

      else
       {
           current = reverse_list_recursive(current);
           parent->next = NULL;
           current->next = parent;
           printf("\n %d \n",current->value);
           return parent;
       }

  }

Answer 2

Я не вижу здесь преимущества рекурсии, итерация будет работать так же хорошо. Это было вечно с тех пор, как я написал C (и нет простого способа проверить следующее на наличие синтаксических ошибок ... или cringe дампов ядра, но вы поймете))

node *reversed_list(node *list) {
    node *fwd=list;//Purely for readability
    node *last=null;
    node *next=null;
    node *rev=null;
    do {
        //Cache next
        next=fwd->next;
        //Set current
        rev=fwd;
        //Reset next to point back
        rev->next=last;
        //Update last
        last=fwd;
        //Forward ptr;
        fwd=next;
    } while (fwd!=null);
    return rev;
}

Уверен, ваш *list бесполезен после того, как вы вызвали его, поскольку теперь он указывает на последний элемент списка, который имеет ->next=null, может просто обновить его вместо возврата указателя.

Обновление (для рекурсивного решения)

Как уже говорили другие, ваш новый хвост испорчен (указывает на последний элемент, но должен указывать на ноль) ... и вы не возвращаете правильную голову, вы возвращаете второй элемент. Рассмотрим список a->b->null с вашим алгоритмом:

p=a,
c=b;
c=
   p=b
   c=null
   return b; //b->null
c=b
c->next=a //b->a
return a; //a->b, b->a, a returned
//But what you wanted is a->null, b->a, and b returned

Исправит следующий обновленный код:

node *reverse_list_recursive(node *list)
  {
      node *parent = list;
      node *current = list->next;

      if(current == NULL)
       return parent;

      else
       {
           current = reverse_list_recursive(current);
           current->next = parent;
           parent->next=null; //Fix tail
           printf("\n %d  %d \n",current->value,parent->value);
           return current; //Fix head
       }

  }

Со списком a->b->null:

p=a,
c=b;
c=
   p=b
   c=null
   return b; //b->null
c=b
c->next=a //b->a
p->next=null //a->null
return b; // b->a->null

Answer 3

Вы забыли обновить next члена первого элемента в связанном списке. Добавьте parent->next = NULL; перед рекурсивным вызовом.

Answer 4

Когда вы достигнете конца списка, вы вернете последний узел.Следующее значение этого последнего узла затем присваивается самому себе, поэтому вы можете создать несогласованность.Если current равен NULL, вместо этого верните NULL и просто игнорируйте остальную часть кода, если возвращаемое значение равно NULL.

Answer 5

Вам нужно установить следующий указатель нового хвоста (т.е. старой головы) в NULL

РЕДАКТИРОВАТЬ: Вот рекурсивная версия

node *reverse_list_recursive(node *list)
  {
      node *parent = list;
      node *child = list->next;
      node *new_head;


    if (child == NULL)
          return parent ;  /* new head */

    new_head = reverse_list_recursive(child)
    child->next = parent; /* Old parent is the new child of the old child when reversed */
    parent->next = NULL; /* might be tail, will be overwritten after we return if we're not at the top level */
    return new_head;
}

Answer 6

Здесь идет рекурсивный код для обращения к связанному списку.

list * reverse(list * head)
{
    if( head == NULL || head -> link == NULL )
        return head;
    list *node = reverse( head- > link );
    head -> link -> link = head;
    head -> link = NULL;
    return node;
}

Answer 7

Некоторые проблемы, которые я мог видеть:

• Вам нужно сделать следующий указатель нового последнего узла NULL.
• Ваша существующая функция сработает, если я передам ей NULL изначально.

Answer 8

После строки current = reverse_list_recursive(current); вы сохраняете новый заголовок списка в текущем, поэтому current->next = parent; неверно.Новый current - это новый заголовок списка, но вам нужно получить доступ к новому хвосту списка, т. Е. OLD current:

node* newhead = reverse_list_recursive(current);
current->next = parent;
printf("\n %d  %d \n",current->value,parent->value);
return newhead;

Answer 9

Версии Severl, описанные выше, не работают так, как хотел OP, поэтому вот моя рекурсивная версия, проверенная отлично:

node * reverseRecursive(node *p,node **head)
{
     if(p->next == NULL)
     {
         *head = p;
          return p;
     }
     node *before;
     before = reverseRecursive(p->next,head);
     before->next = p;
     p->next = NULL;
     return p;
}

//call from main
node*head; 
//adding value
//assuming now head is now 1->2->3->4->NULL
node* newHead;
reverseRecursive(head,&newHead);
//now now newHead is now 4->3->2->1->NULL