时间戳

首页 > 解决方案 > 为什么这两个不同的反向双链表？

c++ - 为什么这两个不同的反向双链表？

问题描述

要反转双向链表，这两个代码有什么区别？和改变next和previous指针不一样吗？

void reverse(Node **head_ref) 
{ 
    Node *temp = NULL; 
    Node *current = *head_ref; 

    while (current != NULL) 
    { 
        temp = current->prev; 
        current->prev = current->next; 
        current->next = temp;             
        current = current->prev; 
    } 

    if(temp != NULL ) 
        *head_ref = temp->prev; 
} 

void reverse(Node **head_ref) 
{ 
    Node *temp = NULL; 
    Node *current = *head_ref; 

    while (current != NULL) 
    { 
        temp = current->next;
        current->next; = current->prev; 
        current->prev = temp;             
        current = current->next; 
    } 

    if(temp != NULL ) 
        *head_ref = temp->next;
}

标签： c++algorithmdata-structuresdoubly-linked-list

解决方案

当您交换两个引用时，您确实可以选择从哪一个开始，即将哪个复制到temp变量中。

所以以下两段代码成功实现了交换：

    temp = current->prev; 
    current->prev = current->next; 
    current->next = temp;

并且（如果您删除了中途的分号）：

    temp = current->next; 
    current->next = current->prev; 
    current->prev = temp;

但是，您的第二个代码块应该像第一个代码块一样继续。您必须点击prev链接（与交换之前的next链接一样）。所以在第二个版本中你应该改变：

    current = current->next;

至：

    current = current->prev;

尽管如此，第二个代码中的问题是，在每次迭代结束时，您的temp引用等于current引用，并且在循环退出时将为空。这样就无法在循环退出后正确设置头指针。

所以你真的应该坚持第一个版本。

推荐阅读