写c语言算法,对无头结点的单链表逆置
时间: 2024-10-14 20:08:13 浏览: 40
在C语言中,对无头结点的单链表逆置可以通过迭代或递归的方式实现。这里提供一种常见的迭代方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
// 函数用于创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 函数用于逆置链表
void reverseList(Node** head) {
if (*head == NULL || (*head)->next == NULL) {
return; // 如果链表为空或只有一个元素,直接返回
}
Node* prev = NULL;
Node* current = *head;
Node* nextTemp = NULL;
while (current != NULL) {
// 保存当前节点的下一个节点
nextTemp = current->next;
// 将当前节点指向其前驱节点
current->next = prev;
// 更新前驱、当前节点指针
prev = current;
current = nextTemp;
}
*head = prev; // 逆置后的头节点
}
// 打印链表
void printList(Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
// 创建示例链表
Node* list = createNode(1);
list->next = createNode(2);
list->next->next = createNode(3);
list->next->next->next = createNode(4);
printf("Original List:\n");
printList(list);
// 逆置链表
reverseList(&list);
printf("\nReversed List:\n");
printList(list);
return 0;
}
```
在这个例子中,`reverseList`函数通过三个指针prev、current和nextTemp来逐步修改链表节点的链接,实现了链表的逆置。
阅读全文