c++ - C++ 反转链表

Question

Possible Duplicate:
Unable to reverse a linked list

我正在尝试反转链接列表:

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(打印功能很好)。

有什么帮助吗？

谢谢

Answer 1

既然你说你想自己找到问题所在，那么我只给你一个提示，而不是解决方案。

您的 reverse 函数可以成功地反转列表。那不是问题。您可能有 2 次调用 print。一张在前，一张在后，相反。在这两种情况下，您对传递给 print 的节点有何注意？这告诉你什么？

编辑:

既然你说你已经找到了问题，我会发布实际的解决方案。

在您的reverse代码中，您永远不会更新列表的_head，但是当您reverse列表时，头实际上会改变从4到1。由于您从不更新 _head，因此当您第二次调用 print 时(在 reverse 调用之后)，您会从 1 处开始打印code>，这是列表的末尾，也是打印的唯一节点。

解决方案是在反转列表时更新_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;
    }
}