c语言数据结构链表实：倒置验

### C语言实现链表倒置 在C语言中，可以通过迭代或递归来实现链表的倒置。以下是基于迭代方法的具体实现方式： #### 定义链表结构体 首先定义链表节点的结构体 `struct Node` 和其指针类型。 ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct Node { int data; struct Node* next; } Node, *ListNode; // 创建新节点函数 Node* create_node(int value) { Node* newNode = (Node*)malloc(sizeof(Node)); if (!newNode) { printf("内存分配失败\n"); exit(1); } newNode->data = value; newNode->next = NULL; return newNode; } ``` --- #### 链表初始化与打印功能 为了便于测试，提供简单的链表初始化和打印功能。 ```c // 初始化链表并插入多个节点 void initialize_list(ListNode* head_ref, int values[], int size) { ListNode current = NULL; for (int i = 0; i < size; ++i) { if (*head_ref == NULL) { *head_ref = create_node(values[i]); current = *head_ref; } else { current->next = create_node(values[i]); current = current->next; } } } // 打印链表内容 void print_list(ListNode head) { while (head != NULL) { printf("%d -> ", head->data); head = head->next; } printf("NULL\n"); } ``` --- #### 实现链表倒置（迭代法） 通过三个指针变量分别跟踪当前节点、前驱节点以及后续节点来完成链表倒置。 ```c // 使用迭代法倒置链表 ListNode reverse_list_iterative(ListNode head) { ListNode prev = NULL; // 前驱节点 ListNode current = head; // 当前节点 ListNode next_temp = NULL; // 后续节点临时保存 while (current != NULL) { next_temp = current->next; // 保存当前节点的下一节点 current->next = prev; // 将当前节点的 next 指向前驱节点 prev = current; // 移动前驱节点到当前位置 current = next_temp; // 移动当前节点到下一位置 } return prev; // 新的头结点为原链表的最后一个节点 } ``` 上述代码逻辑清晰地展示了如何逐步改变链表中的指针方向[^4]。 --- #### 测试代码 以下是一个完整的测试案例，展示如何创建链表、打印初始状态、执行倒置操作后再打印结果。 ```c int main() { int values[] = {1, 2, 3, 4, 5}; int n = sizeof(values) / sizeof(values[0]); ListNode head = NULL; // 初始化链表 initialize_list(&head, values, n); // 打印原始链表 printf("Original List:\n"); print_list(head); // 反转链表 head = reverse_list_iterative(head); // 打印反转后的链表 printf("Reversed List:\n"); print_list(head); return 0; } ``` 运行此程序会得到如下输出： ``` Original List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Reversed List: 5 -> 4 -> 3 -> 2 -> 1 -> NULL ``` --- ### 总结 以上代码实现了单向链表的倒置功能，并提供了详细的注释以便理解每一步的操作过程。该算法的时间复杂度为 O(n)，其中 n 是链表长度，空间复杂度为 O(1)[^4]。