本题要求实现一个函数reverse( ),完成将一带头结点单链表的结点按相反顺序链接,要求仅使用原结点空间,不新开结点空间。 为了讨论简化,我们假设每个数据元素是一个整数:函数无返回值,有一个引用参数L, 用于传递带头单链表的头指针。使用c语言
时间: 2024-09-14 09:15:30 浏览: 58
借助栈将一个带头结点的单链表倒置
4星 · 用户满意度95%
在C语言中,实现一个将单链表反转的函数`reverse()`,可以利用三个指针的概念:当前节点、前一个节点和下一个节点。由于题目要求不使用新的节点空间,我们需要在原地修改链表的连接。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct ListNode {
int data; // 数据域
struct ListNode *next; // 指向下一个节点的指针
} ListNode;
// 反转链表函数
void reverse(ListNode **head) {
if (*head == NULL || (*head)->next == NULL) { // 如果链表为空或只有一个节点,无需反转
return;
}
ListNode *prev = NULL, *current = *head, *nextTemp;
while (current != NULL) { // 遍历整个链表
nextTemp = current->next; // 保存当前节点的下一个节点
current->next = prev; // 将当前节点指向前一个节点
prev = current; // 更新前一个节点为当前节点
current = nextTemp; // 移动到下一个节点
}
*head = prev; // 最终链表的新头节点是原来的尾节点
}
// 测试函数
void printList(ListNode *head) {
ListNode *temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
// 创建测试链表
ListNode *testList = (ListNode*)malloc(sizeof(ListNode));
testList->data = 1;
testList->next = (ListNode*)malloc(sizeof(ListNode));
testList->next->data = 2;
testList->next->next = (ListNode*)malloc(sizeof(ListNode));
testList->next->next->data = 3;
testList->next->next->next = NULL;
printf("Original List: ");
printList(testList);
reverse(&testList); // 调用反转函数
printf("Reversed List: ");
printList(testList);
return 0;
}
```
在这个例子中,`reverse()`函数接收一个指向链表头节点的指针,并在原地改变链表的连接。`main()`函数创建了一个简单的链表并打印出原始链表和反转后的链表。
阅读全文