递归反转字符串链表

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

- Melanie

---

看起来你在构建链表时已经反转了列表。如果你同时跟踪列表的头和尾，处理起来会更容易（在尾部插入，保持头指向第一个元素）。 - Stefan

那么你的意思是我在构建链表时犯了错误？ 在循环内获取新输入的同时，如何最好地保持头指针始终指向第一个输入（循环外）？ 谢谢Stefan！ - Melanie

我认为 Reverse 函数也有问题。你正确地遍历了列表，但我认为当你返回时会丢弃信息。我认为分析这个问题的最好方法是在纸上绘制一个具有 3 个节点的示例列表。至于标题，你可以在循环之前创建一个新节点，然后在循环中填写信息，然后创建下一个节点，仍然在循环中。 - Stefan

使用递归来完成这种任务是一个错误——它只会增加复杂性。 - Dúthomhas

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/

- Lakhshya Bansal

---

如果您希望递归地反转一个链表，您将需要使用双指针。 - Lakhshya Bansal

那么如果我稍后在主函数中使用recursiveReverse函数，我应该插入哪个参数？我尝试使用“head”，但它不兼容。 - Melanie

发送 &head。如果这篇回答对您有帮助，请点赞！ - Lakhshya Bansal