时间戳

首页 > 解决方案 > 如何使用递归反转链表？

c++ - 如何使用递归反转链表？

问题描述

我正在尝试使用递归来反转链表。我之前使用简单的while循环编写了代码来执行此操作，并且效果很好。我不知道为什么我的递归代码不起作用。

#include<iostream>

using std::cout;
using std::endl;

struct node
{
    int data;
    node* next;
};

class LinkedLists
{
    private: 
    node* head;
    node* temp;
    
    public:
    LinkedLists() // default constructor
    {
        head = NULL;
        temp = NULL;
    }

    void add_data(int d)
    {   
        node* new_node = new node; // create a pointer to the new node
        new_node->next = NULL;
        new_node->data = d;
        if (head == NULL)
        {   head = new_node;
            temp = head;
        }
        else
        {   
            temp = head;
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            temp->next = new_node; // final node now points to the new_node
        }

    }

    void print_list()
    {
        temp = head;
        while(temp!=NULL)
        {
            std::cout<<temp->data<<" ";
            temp = temp->next;
        }
    }

    void reverse()
    {
        // reverse a linked list
        node* prev_node;
        node* next_node;
        node* temp_ptr;

        prev_node = NULL;
        temp_ptr = head;
        next_node = temp_ptr->next;

        while(next_node != NULL)
        {
            temp_ptr->next = prev_node;
            prev_node = temp_ptr;
            temp_ptr = next_node;
            next_node = temp_ptr->next;
        }

        temp_ptr->next = prev_node;

        head = temp_ptr;

    }

    void repeat(node* prev_node, node* temp_ptr,node* next_node)
    {
        temp_ptr->next = prev_node;
        prev_node = temp_ptr;
        temp_ptr = next_node;

        if (next_node != NULL)
        {
            next_node = temp_ptr->next;
            repeat(prev_node,temp_ptr,next_node);
        }
        head = temp_ptr;
    }

    void recursive_reverse()
    {
        node* prev_node;
        node* next_node;
        node* temp_ptr;

        prev_node = NULL;
        temp_ptr = head;
        next_node = temp_ptr->next;

        repeat(prev_node,temp_ptr,next_node);

    }
};

int main()
{
    LinkedLists l; // create a linked list object
    l.add_data(110);
    l.add_data(140);
    l.add_data(101);
    l.add_data(140);
    l.add_data(101);
    l.add_data(140);
    l.add_data(101);
    l.add_data(120);

    cout<<endl;
    l.print_list();


    l.reverse();

    cout<<endl;
    l.print_list();


    l.recursive_reverse();
    cout<<endl;
    l.print_list();

}

输出：

110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
101 120

预期输出：

110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
110 140 101 140 101 140 101 120

标签： c++algorithmrecursiondata-structureslinked-list

解决方案

您的代码是多余的，您不需要那么多局部变量和函数参数来实现递归。同样在这部分：

        if (next_node != NULL)
        {
            next_node = temp_ptr->next;
            repeat(prev_node,temp_ptr,next_node);
        }
        head = temp_ptr;

你似乎分配nullptr给你的headwhen next_node == nullptr。

修正版：

    void repeat(node* previous, node* current)
    {
      node* next_node = current->next;
      current->next = previous;
      if (next_node == nullptr)
      {
        head = current;
        return;
      }
      repeat(current, next_node);
    }

    void recursive_reverse()
    {
        repeat(nullptr, head);
    }

除此之外，您还有内存泄漏，因为您从未delete分配过内存。实现析构函数并将复制构造函数/赋值标记为deleted显式（或者如果有时间，也可以实现它们）：

LinkedLists(const LinkedLists& other) = delete;

避免进一步的错误并遵守三（或五，或零）的规则。

推荐阅读