设计一个算法,将链表中所有结点的链接方向“原地”逆转,即要求仅利用原表的存储 空间,换句话说,要求算法的空间复杂度为O(1)。用c代码叙述
时间: 2024-10-01 07:11:56 浏览: 23
设计一个原地逆转链表的算法通常可以采用迭代的方式,通过三个指针分别指向当前节点、前一个节点和后一个节点。以下是C语言描述的一个简单版本:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个元素,无需反转
return head;
}
ListNode* prev = NULL; // 初始化前驱节点为NULL
ListNode* curr = head; // 当前节点初始化为头节点
// 使用循环遍历链表,每次迭代更新prev, curr, next
while (curr != NULL) {
ListNode* nextTemp = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点的next指向前一个节点
prev = curr; // 更新前驱节点为当前节点
curr = nextTemp; // 更新当前节点为之前保存的下一个节点
}
return prev; // 返回新的头节点,链表已经反转
}
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->val);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
// 创建并初始化一个链表示例
ListNode* list = (ListNode*)malloc(sizeof(ListNode));
list->val = 1;
ListNode* second = (ListNode*)malloc(sizeof(ListNode));
second->val = 2;
list->next = second;
second->next = (ListNode*)malloc(sizeof(ListNode));
second->next->val = 3;
second->next->next = NULL;
printf("Original List:");
printList(list);
list = reverseList(list); // 反转链表
printf("\nReversed List:");
printList(list);
return 0;
}
```