反转链接列表，为什么head不指向原始第一个元素？

我正在尝试使用以下程序来反转链接列表。但最后head仍错误地指向原始列表的第一个元素。我在哪里犯错？反转链接列表，为什么head不指向原始第一个元素？

#include <iostream> 

struct node{ 
    node(int val): 
     value(val), 
     next(nullptr) 
    {} 

    ~node(){ 
     delete next; 
     std::cout << "Deleting " << value << std::endl; 
    } 

    int value; 
    node* next; 
}; 

node* create() 
{ 
    node * head = new node(1); 
    head->next = new node(2); 
    head->next->next = new node(3); 
    head->next->next->next = new node(4); 
    head->next->next->next->next = new node(5); 
    return head; 
} 

void print(node* head) 
{ 
    auto ptr = head; 
    while(ptr !=nullptr) 
    { 
     std::cout << ptr->value << " -> " ; 
     ptr = ptr->next; 
    } 
    std::cout << "nullptr" << std::endl; 
} 

void reverse(node** head_p) 
{ 
    auto head = *head_p; 

    auto p2 = head->next; 
    head->next = nullptr; 

    while(p2!=nullptr) 
    { 
     auto temp = head; 
     head = p2; 
     p2 = p2->next; 
     head->next = temp; 
    } 
} 

int main() 
{ 
    auto head = create(); 
    print(head); 

    reverse(&head); 

    print(head); 
    delete head; 
    return 0; 
}

来源

2015-05-06 sank

什么是'删除下一个';'应该在'node'的析构函数中做？ – Lingxi

@灵溪，它删除下一个节点。 – sank

[相关]（http://codereview.stackexchange.com/q/45918/489）。 –

在这个函数：

void reverse(node** head_p) 
{ 
    auto head = *head_p; 

    auto p2 = head->next; 
    head->next = nullptr; 

    while (p2 != nullptr) 
    { 
     auto temp = head; 
     head = p2; 
     p2 = p2->next; 
     head->next = temp; 
    } 
}

除非我读了这个错误，您操纵了列表，但未能更新head_p，这是您通过其地址的head的指针。

来源

2015-05-06 01:15:44

我很困惑。我正在传递变量的地址。不应该在调用者程序中反映这些更改吗？ – sank

@sank，当你做'auto head = * head_p'时，你用'* head_p'指针（即你传递的指针的地址）初始化'head'。所以'head'就像'0xA0FF014'（即一个地址）。要修改该地址处的内容（即，通过指向“reverse”的指针传递的指针），您需要解除引用head。想想你如何修改一个通过指针传递的简单变量，然后你会看到发生了什么。或者，为了简化事情，我建议对'node *'使用'typedef'，那么你的代码将变得更加清晰。 – vsoftco

在你reverse()功能你正在做auto head = *head_p;，但在那之后你不修改指针*head_p。要修改指针*head_p，您需要解除引用head，如*head = nullptr（套数head指向nullptr）。

快速修复：将auto head替换为auto& head以使用对*head_p的引用。或者，更好，只是通过引用传递直接head您reverse()功能，如

void reverse(node*& head_p) 
{ 
    auto p2 = head_p->next; 
    head_p->next = nullptr; 

    while(p2!=nullptr) 
    { 
     auto temp = head_p; 
     head_p = p2; 
     p2 = p2->next; 
     head_p->next = temp; 
    } 
}

并调用它作为

reverse(head);

来源

2015-05-06 01:14:46 vsoftco

我不认为你的修复解决OP的要求“*在最后头仍然指向原始列表的第一个元素。*” – Lingxi

@Lingxi我认为它的工作原理，请参见[这里]（http：// ideone的.com/JMwPsS）。 '头'肯定是修改过的。我认为*“最后头仍然指向原列表的第一个元素。”*是问题，而不是要求:) – vsoftco

@灵溪对不起，我不明白。 OP想要反转一个链表，我的代码正在反转一个链表（这就是为什么我加了一个额外的'reverse（head）; print（head）;'来看看这个链表是否确实颠倒了。我在这里误解了一些东西 – vsoftco

我认为，当我们有做出头的标准库，我们应该使用它们

#include <iostream> 
#include <list> 
#include <algorithm> 

using namespace std ; 

list <int> ls ; 

int main() 
{ 
    ls.push_back(1) ; 
    ls.push_back(2) ; 
    for (auto x : ls){ 
     cout << x << endl ; 
    } 
    reverse (ls.begin() , ls.end()) ; 
    for (auto x : ls){ 
     cout << x << endl ; 
    } 
    return 0; 
}

您可以使用结构列表例如

struct mystruct{ 
    int a , b ; 
    char c ; 
}; 

list <mystruct> ls ;

更多信息，请参阅this

来源

2015-05-07 20:10:21 Reza

反转链接列表，为什么head不指向原始第一个元素？

回答

相关问题