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

Answer 2

这个怎么样:

void revNodes(IntNodePtr&head)
{
    IntNodePtr prev = NULL;
    IntNodePtr next = NULL;
    IntNodePtr p = head;
    while (p){
        next = p->getLink();
        p->setLink(prev);
        prev = p;
        p = next;
    }
    head = prev;
}

Answer 3

你的算法有两个问题:

1. 列表中的head元素将成为反向列表中的最后一个元素，因此您需要将其链接设置为NULL。

2. 在循环的第一次迭代中，您将第二项中的链接更改为指向第一个元素，但您没有将next指针移动到下一项(在本例中为第三个元素)。