反转链表，为什么 head 不应该指向原来的第一个元素？

Question

我正在尝试使用以下程序反转链表。但是最后 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;
}

Answer 1

在您的 reverse() 函数中您正在执行 auto head = *head_p;，但之后您不修改指针 *head_p。要修改指针 *head_p，您需要取消引用 head，例如*head = nullptr（将 head 指向的内容设置为 nullptr）。

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

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

Answer 2

在这个函数中：

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 的指针。

Answer 3

我认为当我们有标准库来做某事时，我们应该使用它们

#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

反转链表，为什么 head 不应该指向原来的第一个元素？

Reversing a linked list, why does head still point to original first element when it should not?

c++

linked-list

c++11