C++ 反转链表：递归实现优化

本文将展示一种简洁高效的 C++ 代码实现，使用递归方法反转链表。

问题描述：

给定一个单链表的头节点，反转该链表。

初始代码:

class Solution {
public:
    int f=0;
    ListNode* ans;
    void dfs(ListNode* p,ListNode* q){
        if(!q) {
            f=1;
            return;
        }
        dfs(q,q->next);
        if(f==1){
            ans = q;
        }
        q->next = p;
    }
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        else{
            dfs(head,head->next);
            return ans;
        }
    }
};

问题分析:

上述代码的实现是对的，但是不够简洁。可以使用递归代替 dfs 函数，避免使用全局变量 f 和 ans，同时代码也更加清晰易懂。

改进后的代码:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }
};

代码解析:

递归终止条件：当链表为空或只有一个节点时，直接返回头节点。
递归过程：
- 递归调用 reverseList(head->next)，将 head->next 之后的链表进行反转，得到新的头节点 p。
- 将 head->next 的 next 指针指向 head，将 head 接到反转后的链表末尾。
- 将 head 的 next 指针指向 nullptr，断开 head 与原链表的连接。
- 返回新的头节点 p。

代码优化:

使用递归代替循环，简化代码结构。
避免使用全局变量，提高代码可读性和可维护性。
减少代码行数，提高代码简洁度。

总结:

本文介绍了使用递归方法反转链表的优化实现，代码简洁高效，易于理解和维护。递归在解决链表反转问题时能够提供清晰直观的解决方案，并能有效减少代码复杂度。