5

Подскажите, как реализовать операцию обращения списка (reverse) в однонаправленном связанном списке?

3 ответа 3

9

Бежишь по списку, первому элементу в поле next указываешь null, а каждому последующему в next предыдущий элемент

5

Для С++, в котором однонаправленный список реализован классом 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;
}
4

Идиома подцепления элемента 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)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.