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

下面是一个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 打印原始链表和反转后的链表。

这样，通过单次遍历，我们可以将链表中的所有节点的链接方向逆转，并继续使用原有存储空间。希望这个示例对你有帮助。