c翻转链表

### C语言实现单链表反转 以下是基于提供的引用以及常见实现方式编写的C语言单链表反转代码。此代码采用递归方法来完成链表的反转。 #### 方法一：递归实现 递归是一种常见的解决链表反转的方法，它通过不断调用自身函数直到到达链表末端再逐步返回并调整指针方向。 ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct Node { int data; struct Node* next; } Node; // 创建新节点 Node* create_node(int value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = NULL; return newNode; } // 打印链表 void print_list(Node* head) { while (head != NULL) { printf("%d ", head->data); head = head->next; } printf("\n"); } // 递归反转链表 Node* reverse_recursive(Node* current, Node* previous) { if (current == NULL) { // 如果当前节点为空，则说明已经到了原链表尾部 return previous; // 返回新的头部节点 } Node* next = current->next; // 保存下一个节点 current->next = previous; // 将当前节点指向前面的节点（即反转） return reverse_recursive(next, current); // 继续处理下一个节点 } int main() { // 初始化链表 Node* head = create_node(1); head->next = create_node(2); head->next->next = create_node(3); head->next->next->next = create_node(4); printf("Original list:\n"); print_list(head); // 调用递归反转函数 head = reverse_recursive(head, NULL); printf("Reversed list:\n"); print_list(head); return 0; } ``` 上述代码展示了如何利用递归来反转一个单向链表[^1]。 --- #### 方法二：迭代实现 另一种常用的方式是使用迭代法，这种方法不需要额外的空间开销，并且逻辑相对简单明了。 ```c #include <stdio.h> #include <stdlib.h> // 结构定义同前... // 迭代反转链表 Node* reverse_iterative(Node* head) { Node* prev = NULL; Node* curr = head; Node* next = NULL; while (curr != NULL) { next = curr->next; // 存储下一节点地址 curr->next = prev; // 当前节点指向前一节点 prev = curr; // 前移prev至当前位置 curr = next; // 移动到下一位继续遍历 } return prev; // 新的头结点为最后的prev位置 } int main() { // 链表初始化... printf("Original list:\n"); print_list(head); // 使用迭代方式进行反转 head = reverse_iterative(head); printf("Reversed list via iteration:\n"); print_list(head); return 0; } ``` 这段程序实现了通过循环一步步修改各节点间连接关系从而达到整个列表反序的效果[^2]。 --- #### 方法三：新建链表（头插法） 如果允许创建一个新的链表作为存储空间的话，那么还可以考虑采取头插法来进行操作——每次都将旧链表上的元素摘除下来插入到新建立起来的那个空闲区域最前端处形成最终结果集。 具体实现在参考资料中有提及[^3]： ```c // 头插法构建新链表... ``` 以上三种方案各有优劣，在实际应用当中可根据具体情况选用合适的一种或者多种组合形式加以运用。 --- ###