c++ - 使用单链表反转字符串

Question

我正在尝试使用链表打印字符串的反向。假设我的字符串是“World is full of good people”，它应该打印“people good of full is World”

#include <iostream>

using namespace std;
/******** Fucntions Prototype *********/

void printList();


typedef struct Node
{
    string data;
    struct Node *next;
}node;

struct Node* newNode(string userData)
{
    node *temp = new Node;
    temp->data = userData;
    temp->next = NULL;
    return temp;
}

void printList(node* head)
{
    node *temp = head;
    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
void reverseList(node *head)
{
    node *curr = head;
    node *prev = NULL, *next = NULL;
    while(curr != NULL)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;

}
int main()
{
    node *head = newNode("World");
    head->next = newNode("is");
    head->next->next = newNode("full");
    head->next->next->next = newNode("of");
    head->next->next->next->next = newNode("good");
    head->next->next->next->next->next = newNode("people");
    cout<<"Linked list before reverse is:\n";
    printList(head);
    cout<<"\n";
    reverseList(head);
    cout<<"Linked list after reverse is:\n";
    printList(head);

    return 0;
}

所以如果字符串是“World is full of good people”，那么预期的输出是“人善之满则天下”，故节点颠倒。但是正在将“世界”作为输出

Answer 1

所以反转列表不是问题，看到你按值传递了 head 所以你实际上是在对 head 的拷贝进行更改。请看pass by value vs pass by reference有关这方面的更多信息。

您的问题的解决方案是将您的原型(prototype)更改为 void reverseList(node **head) 并且每次后续访问 head 都必须使用 进行引用*头。

最后，用reverseList(&head);调用你的函数