（2）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

下面是一个C语言的算法，用于在单次遍历后将单链表中所有节点的链接方向逆转，并利用原表的存储空间： ```c #include <stdio.h> #include <stdlib.h> // 定义单链表的节点结构 typedef struct Node { int data; // 节点存储的数据 struct Node* next; // 指向下一个节点的指针 } Node; // 创建一个新节点 Node* createNode(int value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = NULL; return newNode; } // 在链表末尾添加节点 void appendNode(Node** head, int value) { Node* newNode = createNode(value); if (*head == NULL) { *head = newNode; return; } Node* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } // 打印链表 void printList(Node* head) { Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } // 反转链表 Node* reverseList(Node* head) { Node* prev = NULL; Node* current = head; Node* next = NULL; // 遍历链表并反转 while (current != NULL) { next = current->next; // 保存下一个节点 current->next = prev; // 反转当前节点的指向 prev = current; // 前一个节点前移 current = next; // 当前节点前移 } // prev是新的头节点 return prev; } int main() { Node* head = NULL; // 创建一个空链表 // 在链表中添加一些节点 appendNode(&head, 10); appendNode(&head, 20); appendNode(&head, 30); appendNode(&head, 40); appendNode(&head, 50); // 打印原链表 printf("Original list: "); printList(head); // 反转链表 head = reverseList(head); // 打印反转后的链表 printf("Reversed list: "); printList(head); return 0; } ``` ### 算法说明： 1. **创建链表：** - `Node` 类型用于表示链表中的每个节点。 - `createNode` 函数创建一个新的节点，并初始化数据。 - `appendNode` 函数在链表末尾添加一个新节点。 2. **遍历链表并反转：** - `reverseList` 函数接受链表头节点，并通过三个指针（`prev`, `current`, `next`）逐一反转每个节点的指向。 步骤： - `prev` 初始化为 `NULL`。 - `current` 初始化为链表头节点。 - 在每次循环中，保存 `current` 的下一个节点到 `next`。 - 反转 `current` 的指向，即将其指向 `prev`。 - 将 `prev` 和 `current` 向前移动到下一个节点。 3. **主函数：** - 创建一个空链表并添加一些整数节点。 - 调用 `reverseList` 反转链表。 - 使用 `printList` 打印原始链表和反转后的链表。 这样，通过单次遍历，我们可以将链表中的所有节点的链接方向逆转，并继续使用原有存储空间。希望这个示例对你有帮助。