递归实现单链表的反转 【问题描述】 已知 f 为单链表的表头指针,试写出求单链表转置的递归算法。

好的，递归实现单链表的反转可以按照以下步骤来实现：

1. 如果链表为空或只有一个节点，直接返回该节点。

2. 递归反转除第一个节点外的子链表。

3. 将第一个节点插入到反转后子链表的尾部。

4. 返回新链表的表头指针。

以下是递归实现单链表反转的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义链表结构体
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 递归函数
ListNode* reverseList(ListNode* head) {
    // 如果链表为空或只有一个节点，直接返回该节点
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 递归反转除第一个节点外的子链表
    ListNode* newHead = reverseList(head->next);

    // 将第一个节点插入到反转后子链表的尾部
    head->next->next = head;
    head->next = NULL;

    // 返回新链表的表头指针
    return newHead;
}

// 主函数
int main() {
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = 1;

    ListNode* p1 = (ListNode*)malloc(sizeof(ListNode));
    p1->val = 2;

    ListNode* p2 = (ListNode*)malloc(sizeof(ListNode));
    p2->val = 3;

    ListNode* p3 = (ListNode*)malloc(sizeof(ListNode));
    p3->val = 4;

    ListNode* p4 = (ListNode*)malloc(sizeof(ListNode));
    p4->val = 5;

    head->next = p1;
    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = NULL;

    // 反转链表
    ListNode* newHead = reverseList(head);

    // 输出反转后的链表
    while (newHead != NULL) {
        printf("%d ", newHead->val);
        newHead = newHead->next;
    }

    return 0;
}

希望这个例子能够帮助您理解如何使用递归来实现单链表反转。