反转链表 C++ [重复]

可能的重复：
无法反转链表

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

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（打印功能很好）。

有什么帮助吗？

Thanks

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

Your reverse函数的工作原理是它成功地反转了列表。那不是问题。您可能有 2 个电话print。一张在前，一张在后，相反。关于传递给的节点，您需要注意什么print在这两种情况下？这告诉你什么？

EDIT:

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

In your reverse代码，你永远不会更新_head列表中的，但是当你reverse列表中，头部实际上改变了4 to 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;
    }
}