c++链表反转 - 指针不前进

Question

我知道之前有人问过关于反向链表的问题，但我想尝试用我自己的实现来解决这个问题。

我的代码对我来说很有意义，我觉得它应该可以工作，但是当我运行调试器时，循环无限运行。具体来说，head和next在链表的第一个和第二个节点之间保持交替。 getLink() 方法返回节点的指针(指向列表中的下一个节点)。基于我在 while 循环下的评论的任何输入都会有所帮助。

void revNodes(IntNodePtr& head)
{
    IntNodePtr prev = NULL;
    IntNodePtr next = NULL;
    next = head;
    while (next != NULL)
    {
        prev = head;
        // this should advance the pointer head to the next node in the list because next is the same as head initially
        head = next->getLink();
        // advance the pointer next to node after it
        next = next->getLink();
        // set the pointer in the node that head is pointing to to prev (head before head was advanced)
        head->setLink(prev);
    }
}

Answer 1

您将 next 初始化为 head，然后在循环中将它们设置为都指向相同 节点。

实际上，它们都指向列表头部之后的第一个节点，然后您将该节点上的指针设置为列表头部，行 head->setLink(prev )。因此，在您的下一次循环中，head 和 next 都指向原来的头节点!

如果你改变:

next = next->getLink();

到:

next = head->getLink();

您将能够在列表中前进，但是然后您将跳转下一个节点，因为您将 head 设置为 next->getLink( )。所以一开始你应该初始化next为head->getLink()，在里面设置head为next循环，next 到 head->getLink()，如上。

因此将其转化为代码:

void revNodes(IntNodePtr& head)
{
    IntNodePtr prev = NULL;
    IntNodePtr next = NULL;
    next = head->getLink();
    while (next != NULL)
    {
        prev = head;
        // this should advance the pointer head to the next node in the list
        head = next;
        // advance the pointer next to node after it
        next = next->getLink();
        // set the pointer in the node that head is pointing to to prev (head before head was advanced)
        head->setLink(prev);
    }
}