反转 LinkedList C++ [英] Reverse a LinkedList 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

Lets say the list is: 4->3->2->1

打印列表的时候只看到1个(打印功能不错)

When I print the list, I only see 1 (The print function is good).

有什么帮助吗?

谢谢

推荐答案

既然你说要自己找问题，那我就给你一个提示，而不是解决方案.

Since you said you wanted to find the problem on your own, I'll just give you a hint instead of the solution.

您的 reverse 函数的工作原理是它成功地反转了列表.那不是问题.您可能有 2 次调用 print.一前一后倒.在这两种情况下，您对传递给 print 的节点有什么注意事项?这告诉你什么?

Your reverse function works in that it successfully reverses the list. That isn't the problem. You probably have 2 calls to print. One before and one after the reverse. What do you note about the nodes being passed to print in both cases? What does that tell you?

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

Since you said you've found the problem, I'll post the actual solution.

在你的 reverse 代码中，你永远不会更新列表的 _head，但是当你 reverse 列表时，头部确实改变了从 4 到 1.因为你从不更新 _head，当你第二次调用 print 时(在 reverse 调用之后)你开始打印 1，这是列表的末尾，这是唯一打印的节点.

In your reverse code, you never update the _head of the list, but when you reverse the list, the head does actually change from 4 to 1. Since you never update _head, when you call print the second time (after the reverse call) you start printing at 1, That being the end of the list, that's the only node printed.

解决方案是在反转列表时更新_head.最简单的方法是在每次迭代中简单地更新它.这可能比其他可能的解决方案效率稍低，但它不会改变算法的时间复杂度——它仍然是 O(n):

The solution is to update _head when you reverse the list. The simplest way to do this is to simply update it in each iteration. This may be slightly less efficient than other possible solutions, but it doesn't change the time complexity of the algorithm -- it's still 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;
    }
}

这篇关于反转 LinkedList C++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！