Обратный LinkedList С++

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

Ваша функция reverse работает в том смысле, что она успешно переворачивает список. Это не проблема. Вероятно, у вас есть 2 звонка на print. Один до и один после реверса. Что вы заметили в отношении узлов, передаваемых print в обоих случаях? О чем тебе это говорит?

РЕДАКТИРОВАТЬ:

Поскольку вы сказали, что нашли проблему, я опубликую фактическое решение.

В вашем коде reverse вы никогда не обновляете _head списка, но когда вы reverse списка, заголовок действительно меняется с 4 на 1. Поскольку вы никогда не обновляете _head, когда вы вызываете print во второй раз (после вызова reverse), вы начинаете печатать с 1, это конец списка, это единственный напечатанный узел.

Решение состоит в том, чтобы обновить _head, когда вы переворачиваете список. Самый простой способ сделать это — просто обновлять его на каждой итерации. Это может быть немного менее эффективным, чем другие возможные решения, но это не меняет временную сложность алгоритма - это все еще O (n):

void LinkedList::reverseList()
{
    Node *next=_head;
    Node *prev=0;
    while(next!=0)
    {
        Node *tmp=next->_next;
        next->_next=prev;
        _head = next;
        prev=next;
        next=tmp;
    }
}

Попробуйте что-нибудь вроде этого.

Двусвязный список:

for (Node * n = _head, * next; ; n = next)
{
    next = n->next;

    std::swap(n->next, n->prev);

    if (next == NULL) { _head = n; break; }
}

Односвязный список:

for (Node * n = _head, * prev = NULL, * next; ; prev = n, n = next)
{
    next = n->next;

    n->next = prev;

    if (next == NULL) { _head = n; break; }
}

мне нравится рекурсия; Это легче понять и проверить;

Node* LinkedList::reverseList() { // returns tail
  if (!_head || !_head->_next)
      return _head;
  Node* const h = _head;
  _head = _head->_next;
  h->_next = NULL;
  return reverseList()->_next = h;
}