设计一个算法,利用单链表原来的节点空间逆转一个单链表。要求用c语言实现
时间: 2023-06-18 17:06:27 浏览: 57
可以使用三个指针prev、curr、next来完成单链表的逆转,具体步骤如下:
1. 初始化prev指针为NULL,curr指针为链表头节点。
2. 循环遍历单链表,每次将curr指针指向的节点的next指针指向prev指针指向的节点,然后将prev指针指向curr指针指向的节点,curr指针指向原来节点的下一个节点。
3. 直到curr指针为NULL时,遍历结束,返回prev指针指向的节点,即为逆转后的链表头节点。
以下是C语言实现代码:
```c
#include<stdio.h>
#include<stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *prev = NULL;
struct ListNode *curr = head;
struct ListNode *next = NULL;
while(curr != NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
int main(){
// 创建一个单链表
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = 1;
head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->val = 2;
head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->next->val = 3;
head->next->next->next = NULL;
// 输出原来的单链表
printf("Original List: ");
struct ListNode *curr = head;
while(curr != NULL){
printf("%d ", curr->val);
curr = curr->next;
}
printf("\n");
// 逆转单链表
struct ListNode *newHead = reverseList(head);
// 输出逆转后的单链表
printf("Reversed List: ");
curr = newHead;
while(curr != NULL){
printf("%d ", curr->val);
curr = curr->next;
}
printf("\n");
return 0;
}
```
输出结果为:
```
Original List: 1 2 3
Reversed List: 3 2 1
```