用递归算法逆置一个带头结点的单链表

在C语言中，使用递归算法来逆置一个单链表可以分为两个部分：首先创建一个递归函数，然后处理基本情况和递归情况。下面是一个简单的示例代码： ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct Node { char data; struct Node* next; } Node; // 用于递归逆置链表的辅助函数 Node* reverseHelper(Node* head, Node** tail) { if (head == NULL || head->next == NULL) { // 基本情况：空链表或只有一个节点 *tail = head; // 如果到达最后一个节点，设置tail指向它 return NULL; } Node* newTail = *tail; // 将当前tail指向下个节点 Node* temp = head->next; head->next = NULL; // 避免形成环路 // 递归调用，将剩余部分逆置 reverseHelper(temp, &newTail); *tail = head; // 更新tail为新的头部 temp->next = newTail; // 现在把原头接到逆序后的链表尾部 return temp; } // 主函数：初始化链表并调用逆置函数 void reverseList(Node** head) { Node* oldHead = *head; *head = reverseHelper(*head, &oldHead); // 逆置链表，并更新head } // 插入节点到链表 void insertNode(Node** head, char data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = *head; *head = newNode; } // 打印链表 void printList(Node* head) { while (head != NULL) { printf("%c -> ", head->data); head = head->next; } printf("NULL\n"); } int main() { // 初始化链表示例 Node* head = NULL; insertNode(&head, 'A'); insertNode(&head, 'B'); insertNode(&head, 'C'); insertNode(&head, 'D'); printf("Original List:\n"); printList(head); reverseList(&head); printf("\nReversed List:\n"); printList(head); return 0; } ``` 在这个例子中，`reverseList`函数负责调用递归辅助函数`reverseHelper`，而`reverseHelper`则是递归地逆置链表的部分。当链表只剩下一个节点或为空时，递归结束。

逆置一个带头结点的单链表通常使用递归的方法可以分为两步： 1. **基本情况**：如果链表为空或只有一个节点，那么它本身就是逆置后的结果，所以直接返回原头结点作为新的头结点。 2. **递归步骤**：对于非空链表，可以将它的剩余部分逆置，然后将当前节点指向下部逆置后的头节点，这样就实现了整体链表的逆置。 以下是递归函数的设计示例（假设`LinkNode`包含`data`字段和`next`指针）： ```cpp LinkNode* Reverse(LinkNode* p) { // 基本情况：如果链表为空或只有一个节点 if (!p || !p->next) return p; // 递归步骤：先处理剩余部分，然后连接到当前节点的反转 LinkNode* newHead = Reverse(p->next); // 递归调用 p->next->next = p; // 将p移动到新头部 p->next = nullptr; // 更新p的next指向null return newHead; } ``` 这个函数会返回逆置后的新链表的头节点。如果你需要一个带头结点的完整链表，你可以调用`Reverse(head)`并将返回值赋给`head`。