反转链表时头递归和尾递归有什么区别？

Question

我正在学习在 C++ 中反转链表的不同递归方法。我已经实现了头递归方法和尾递归方法，但我不确定它们的差异以及哪一种更优化。

哪种类型的递归编写最适合使用递归反转链表 1.头递归 2.尾递归

Answer 1

这是我使用头递归的实现：

#include <iostream>
using namespace std;

struct node {
    int data;
    node* next;
    node(int val) : data(val), next(nullptr) {}
};

node* reverse(node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    node* rest = reverse(head->next); // Reverse the rest of the list
    head->next->next = head;          // Adjust the next pointer of the next node
    head->next = nullptr;             // Set the next pointer of the current node to nullptr
    return rest;                      // Return the new head of the reversed list
}

// Helper function to print the linked list
void printList(node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
    node* head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    head->next->next->next->next = new node(5);

    // Print the original linked list
    cout << "Original list: ";
    printList(head);

    // Reverse the linked list using head recursion
    head = reverse(head);

    // Print the reversed linked list
    cout << "Reversed list using head recursion: ";
    printList(head);

    return 0;
}

这是我使用尾递归的实现：

 #include <iostream>
    using namespace std;
    
    struct node {
        int data;
        node* next;
        node(int val) : data(val), next(nullptr) {}
    };
    
    node* helper(node* current, node* prev) {
        if (current == nullptr) {
            return prev;
        }
        node* next = current->next;
        current->next = prev;
        return helper(next, current); // Tail recursion
    }
    
    node* tailReverse(node* head) {
        return helper(head, nullptr);
    }
    
    // Helper function to print the linked list
    void printList(node* head) {
        while (head != nullptr) {
            cout << head->data << " ";
            head = head->next;
        }
        cout << endl;
    }
    
    int main() {
        // Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
        node* head = new node(1);
        head->next = new node(2);
        head->next->next = new node(3);
        head->next->next->next = new node(4);
        head->next->next->next->next = new node(5);
    
        // Print the original linked list
        cout << "Original list: ";
        printList(head);
    
        // Reverse the linked list using tail recursion
        head = tailReverse(head);
    
        // Print the reversed linked list
        cout << "Reversed list using tail recursion: ";
        printList(head);
    
        return 0;
    }

**分析

链表大小：4 个节点（1 -> 2 -> 3 -> 4）**

头递归方法

第一次调用：reverse(head)，其中 head 指向节点 1。

第二次调用：reverse(head->next)，其中 head->next 指向节点 2。

第三次调用：reverse(head->next)，其中 head->next 指向节点 3。

第四次调用：reverse(head->next)，其中 head->next 指向节点 4。

第五次调用：reverse(head)，其中 head 现在为 nullptr。

一旦达到基本情况，每个调用都会以相反的顺序返回，并对指针进行调整：

第四次调用（节点4）返回。

第三次调用（节点3）返回，调整节点4的next指针。

第二次调用（节点2）返回，调整节点3的next指针。

第一次调用（节点1）返回，调整节点2的next指针。

总共有 4 个函数调用到达基本情况，4 个函数返回来调整指针，总共 8 个函数调用。

尾递归方法

第一次调用：reverseUtil(head, nullptr)，其中 head 指向节点 1，prev 为 nullptr。

第二次调用：reverseUtil(head->next, head)，其中 head 指向节点 2，prev 指向节点 1。

第三次调用：reverseUtil(head->next, head)，其中 head 指向节点 3，prev 指向节点 2。

第四次调用：reverseUtil(head->next, head)，其中 head 指向节点 4，prev 指向节点 3。

第五次调用：reverseUtil(head->next, head)，其中 head 为 nullptr，prev 指向节点 4。

总共有 4 次函数调用到达基本情况，1 次从基本情况返回，总共 5 次函数调用。

结论： 头递归方法：总共 8 次函数调用（4 次调用到达基本情况，4 次返回调整指针）。 尾递归方法：总共 5 次函数调用（4 次调用达到基本情况，1 次最终返回）。