c++ - 递归地反转字符串链表

Question

我想首先创建一个包含用户字符串的链表(直到用户输入句号)，然后递归地反转它，然后打印新列表。 下面的程序是我到目前为止得到的:它正在编译但只显示最后一个词。我估计在某个时候我正在将一个新字符串分配给以前的字符串之一的内存位置。 我是 C++ 的新手，想不起我出错的那一刻。 任何意见或提示将不胜感激! 谢谢

#include <iostream>
#include <string>
using namespace std;

//create a node that reads a string and points to next one
struct Node
{
    string word;
    Node * next;
};

//create current and temporary pointers for Node
Node * current;
Node * temp;

//function to reverse Node
void Reverse(struct Node * p, Node * hdr)
{
    if (p->next == NULL)
    {
        hdr = p;
        return;
    }
    Reverse(p->next, hdr);
    struct Node * q = p->next;
    q->next = p;
    p->next = NULL;
    return;
    }

//function to print linked list
void print(Node * header)
{
    cout << "The reversed linked list is: " << endl;
    Node * ptr = header;
    while(ptr!=NULL)
    {
        cout << ptr->word << " ";
        ptr = ptr->next;
    }
}

int main()
{
    //Ask user to input keyboard strings
    cout << "Please insert strings seperated by white spaces (isolated    full-stop to finish): " << endl;
    string input;

    //create head pointer
    Node * head = new Node;
    head->next = NULL;

    //create loop to read words and insert them into linked list
    while(true)
    {
        cin >> input;
        if (input == ".")
            break;
        current = new Node;
        current->word = input;
        current->next = head->next;
        head->next = current;
    }

    //get and output reversed linked list
    Reverse(current, head);
    print(head);
    cout << " ." << endl;

    return 0;
}

Answer 1

试试这个:

void recursiveReverse(struct node** head_ref)
{
    struct node* first;
    struct node* rest;

    /* empty list */
    if (*head_ref == NULL)
       return;   

    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref;  
    rest  = first->next;

    /* List has only one node */
    if (rest == NULL)
       return;   

    /* reverse the rest list and put the first element at the end */
    recursiveReverse(&rest);
    first->next->next  = first;  

    /* tricky step -- see the diagram */
    first->next  = NULL;          

    /* fix the head pointer */
    *head_ref = rest;              
}

引用http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/