0

我正在尝试使用迭代方法来反转双向链表，即使我没有使用指向原始列表的指针样式修改的指针，我也对正在修改原始列表的部分感到震惊。

这是我正在使用的反向函数，head是在 main 中声明的局部变量，Node* head = NULL;并且已经填充了一组值。 

Node* reverse_iterative(Node* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    Node *prev, *current=head, *temp;
    while(current != NULL)
    {
        current->prev = current->next;
        current->next = temp;
        temp = current;
        current = current->prev;
    }
    return temp;
}

这就是我在 main 中使用它的方式：

Node* rev = NULL;
rev = reverse_iterative(head);

这是我得到的输出：

original list: 15 <=>25 <=>35 <=>45 <=>55 <=>65 <=>75 <=>
making the list actually reverse: 75 <=>65 <=>55 <=>45 <=>35 <=>25 <=>15 <=>
after reversing, the original list now: 15 <=>

我无法获得修改原始头节点的部分。

4

2 回答 2

3

仔细查看您的 while 循环，并考虑以下关于循环初始迭代的语句：

current->next = temp;

temp执行此任务时有什么内容？暴露更多代码，我们有：

Node *prev, *current=head, *temp;
while(current != NULL)
{
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

请注意， temp 未初始化，因此是未定义的指针值。您原来的 head-ptr next ptr 被重置为保存在未初始化温度中的垃圾。

通过执行以下操作解决此问题：

Node *current=head, *temp=NULL;
while(current != NULL)
{
    temp = current->prev;
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

我没有机会对其进行测试，但这应该可以让您更接近您正在寻找的东西。

于 2012-10-29T19:37:55.353 回答
3

如果我理解正确，您根本不希望您的原始列表被修改。

但是循环修改了原始元素。例如，current 开始指向 head 元素，然后您修改它的 next 和 prev。这意味着现在修改了原始的 head 元素。

于 2012-10-29T19:49:10.850 回答