设计文档：链表逆置模块
- 问题描述
本题要求实现一个函数，将给定的单向链表逆置，即表头置为表尾，表尾置为表头。给定链表的节点结构如下：
c
struct ListNode {
int data;
struct ListNode *next;
};
函数接口如下：
c
struct ListNode *reverse(struct ListNode *head);
其中，head 是用户传入的链表的头指针。该函数需要将链表逆置，并返回逆置后的链表头指针。
- 函数功能
函数的核心功能是将单向链表逆置。具体而言：
输入：单向链表的头节点 head。
输出：逆置后的单向链表的头节点。
3. 算法设计
链表逆置的基本思路是通过修改节点的 next 指针来反转链表的方向。
初始化一个 prev 指针，表示已经处理的部分，初始化为 NULL。
遍历链表，每次更新当前节点的 next 指针，使其指向前一个节点。
依次处理链表中的每个节点，直到遍历完链表。
具体步骤：
初始化 prev 为 NULL，curr 为链表的头节点。
遍历链表，对于每个节点：
保存当前节点的下一个节点 next。
将当前节点的 next 指针指向 prev，即反转指向关系。
移动 prev 和 curr 指针向前。
最终，prev 会指向链表的最后一个节点，即新的头节点。
4. 模块图
由于目前不支持插入图片，因此请参考以下文本描述手绘模块图：
+------------------------+
| 输入：链表头节点 head |
+------------------------+
|
V
+------------------------+
| 初始化指针 prev=NULL |
+------------------------+
|
V
+------------------------+
| 遍历链表，更新指针 next |
+------------------------+
|
V
+------------------------+
| 返回反转后的头节点 |
+------------------------+
5. 代码实现
c
include <stdio.h>
include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
// 反转链表函数
struct ListNode *reverse(struct ListNode *head) {
struct ListNode *prev = NULL, *curr = head, *next = NULL;
// 遍历链表
while (curr != NULL) {
next = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 反转当前节点的next指针
prev = curr; // prev向后移动
curr = next; // curr向后移动
}
return prev; // 返回新的头节点
}
// 辅助函数：创建链表
struct ListNode *createlist() {
int value;
struct ListNode *head = NULL, *tail = NULL;
// 输入链表数据
while (scanf("%d", &value) && value != -1) {
struct ListNode *new_node = (struct ListNode *)malloc(sizeof(struct ListNode));
new_node->data = value;
new_node->next = NULL;
if (head == NULL) {
head = new_node;
tail = new_node;
} else {
tail->next = new_node;
tail = new_node;
}
}
return head;
}
// 打印链表
void printlist(struct ListNode *head) {
struct ListNode *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
struct ListNode *head;
// 创建链表并逆置
head = createlist();
head = reverse(head);
// 打印逆置后的链表
printlist(head);
return 0;
}
6. 代码解释
reverse 函数：
prev 指针用来记录已反转部分的尾节点。
curr 指针用来遍历链表中的节点。
next 用来保存当前节点的下一个节点，以避免断链。
反转过程中，每次将当前节点的 next 指针指向 prev，然后更新 prev 和 curr。
最终返回的 prev 是反转后的链表头。
createlist 函数：
动态创建链表，直到输入 -1 时停止。
每个新节点通过 malloc 创建，并将其链接到链表的尾部。
printlist 函数：
遍历链表并打印每个节点的数据。
7. 测试样例
输入样例：
1 2 3 4 5 6 -1
输出样例：
6 5 4 3 2 1
8. 时间与空间复杂度
时间复杂度：
由于我们只需要遍历链表一次，时间复杂度为 O(n)，其中 n 是链表中的节点数。
空间复杂度：
我们只使用了常数空间存储指针，因此空间复杂度为 O(1)。
- 总结
该函数实现了链表的反转，并通过指针操作实现了高效的反转算法。函数遵循链表的基本操作原则，时间和空间复杂度均为最优解。