Подскажите, как реализовать операцию обращения списка (reverse) в однонаправленном связанном списке?
3 ответа
Бежишь по списку, первому элементу в поле next
указываешь null
, а каждому последующему в next
предыдущий элемент
Для С++, в котором однонаправленный список реализован классом forward_list
, достаточно вызвать функцию-член reverse()
:)
Для С - что-то вроде
struct Node
{
//...
struct Node * next;
};
void reverse(struct Node ** head)
{
if (*head == NULL) return;
struct Node * curr, *next, *prev = NULL;
curr = *head;
while(curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
Идиома подцепления элемента node
в начало односвязного списка list
элементарна и состоит из двух действий
node->next = list;
list = node;
Все, что надо сделать в данном случае - это пробежаться по исходному списку и последовательно перецепить все его элементы в начало нового списка. Полученный в результате список будет обращением исходного списка
Node *reverse_list(Node *list)
{
Node *reversed_list = NULL;
for (Node *node = list, *next_node; node != NULL; node = next_node)
{
next_node = node->next;
node->next = reversed_list;
reversed_list = node;
}
return reversed_list;
}
В качестве заметки на полях: это одна из тех довольно часто встречающихся ситуаций, когда в языках С и С++ ощущается нехватка операции "сдвигающего присваивания", т.е. некоей компактно записываемой операции
a <- b <- c <- d
эквивалентной
(a = b, b = c, c = d)