递归反转字符串链表

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/