Ошибка сегментации в функции для реверсирования односвязного списка

Question

Я реализую функцию рекурсивного обращения к связанному списку, но получаю ошибку seg.

typedef struct _node {
   int data;
   struct _node *next;
} Node, *NodeP;

NodeP recursiveReverseList(NodeP first){
   if(first == NULL) return NULL;
   if(first->next == NULL) return first;

   NodeP rest = recursiveReverseList(first->next);
   rest->next = first;
   first->next = NULL;

   return first;
}

Не могли бы вы помочь?

P.S. Итерационная версия работает нормально, хотя. Это не домашняя работа. Просто практикую C.

Спасибо всем:)

Answer 1

Общий рекурсивный алгоритм для этого:

1. Divide список в 2 частях - первый узел и остальная часть списка.
2. Рекурсивный обратный вызов для rest связанный список.
3. Ссылка rest на first.
4. Исправлено head Указатель

Вы делаете шаги 1 и 2 правильно, но я думаю, что вы запутались в шагах 3 и 4. Я бы предложил вам попробовать это:

NodeP recursiveReverseList(NodeP first){
   if(first == NULL) return NULL; // list does not exist.
   if(first->next == NULL) return first; // list with only one node.

   NodeP rest = recursiveReverseList(first->next); // recursive call on rest.
   //rest->next = first; CHANGE THIS
   first->next->next = first; // make first next to the last node in the reversed rest.

   first->next = NULL; // since first is the new last..make its next NULL.

   //return first; CHANGE THIS
   return rest; // rest now points to the head of the reversed list.
}

изображение http://geeksforgeeks.org/wp-content/uploads/2009/07/Linked-List-Rverse.gif.

EDIT:

PS: я не проверял это. Так что попробуйте и дайте нам знать:)

Я протестировал вышеуказанную функцию и, похоже, работает как ожидалось. Вы можете попробовать программу здесь: http://ideone.com/bQXAV

Answer 2

@ Unicornaddict уже опубликовал правильный алгоритм.

Но, если вы все еще получаете segmentation fault, я подозреваю, что вы делаете какую-то ошибку при вызове функции из main.

Правильно:

head->next = recursiveReverseList(head->next);

Пояснение:

• Передать head->next в рекурсивную функцию. Если вы передадите head, он сделает что-то вроде

До звонка:
голова ---> A ---> B ---> C
После звонка:
голова <--- A <--- B <--- C </strong>

, который заставит head указать на NULL и A указать на head

• После передачи head->next в качестве аргумента состояние списка:

голова ---> A <--- B <--- C </strong>

Итак, вам нужно head указать на rest (C в данном случае).

Answer 3

Ваш алгоритм кажется неправильным. Вам необходимо вернуть указатель на заголовок нового списка, но вы возвращаете указатель на последний элемент.

Действительно, вам, возможно, понадобятся оба: указатель на голову и указатель на последний элемент.

Answer 4

я думаю

rest->next = first;

должно быть

first->next->next = first;