связанный список — обратное переполнение стека LinkedList

Question

связанный список — обратное переполнение стека LinkedList

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

Я пытаюсь перевернуть связанный список:

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

Допустим, список: 4-> 3-> 2-> 1

Когда я печатаю список, я вижу только 1 (функция печати хороша).

Любая помощь?

Спасибо

2

c++linked-list reversing

Решение

Другие решения

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

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

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; }
}

1

Мне нравится рекурсия; Проще понять и проверить;

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;
}

0

Источник

Accepted Answer

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

Ваш 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;
}
}

2