admin 管理员组文章数量: 1086019
2024年4月21日发(作者：c语言组个最小数)
单链表的逆置c语言算法
单链表的逆置C语言算法
前言：
单链表是一种常用的数据结构，它由一系列节点组成，每个节点包
含数据和指向下一个节点的指针。单链表的逆置是指将链表中的节
点顺序颠倒，即原链表的第一个节点变为新链表的最后一个节点，
原链表的最后一个节点变为新链表的第一个节点。逆置链表在实际
应用中有着重要的作用，例如链表的搜索、排序和删除等操作。
算法思路：
对于单链表的逆置，我们可以利用三个指针来辅助完成。假设原链
表为A->B->C->D->NULL，逆置后的链表为D->C->B->A-
>NULL。初始时，我们定义三个指针：当前指针cur指向当前节点
A，前一个指针prev指向当前节点的前一个节点（初始时为NULL），
下一个指针next指向当前节点的下一个节点（初始时为B）。然后，
我们将当前节点的指针指向前一个节点，即将A->B的指针改为
A<-B。接下来，我们将prev指针指向当前节点，即prev指向A。
最后，我们将cur指针指向next节点，即cur指向B。重复以上操
作，直到cur指针指向NULL，即遍历完整个链表。最后，我们返
回prev指针，即逆置后的链表的头节点。
具体实现：
下面是单链表逆置的C语言代码实现：
```c
#include
#include
// 定义链表节点结构体
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;
}
// 逆置链表
Node* reverseList(Node* head) {
Node* prev = NULL;
Node* cur = head;
Node* next = NULL;
while (cur != NULL) {
next = cur->next; // 保存当前节点的下一个节点
cur->next = prev; // 当前节点的指针指向前一个节点
prev = cur; // prev指针指向当前节点
cur = next; // cur指针指向下一个节点
}
return prev; // 返回逆置后的链表头节点
}
// 打印链表
void printList(Node* head) {
Node* cur = head;
while (cur != NULL) {
printf("%d -> ", cur->data);
cur = cur->next;
}
printf("NULLn");
}
int main() {
// 创建链表 A->B->C->D->NULL
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
printf("原链表：");
printList(head);
// 逆置链表
Node* newHead = reverseList(head);
printf("逆置后的链表：");
printList(newHead);
return 0;
}
```
运行结果：
原链表：1 -> 2 -> 3 -> 4 -> NULL
逆置后的链表：4 -> 3 -> 2 -> 1 -> NULL
总结：
通过三个指针的相互转换，我们可以实现单链表的逆置。这个算法
的时间复杂度为O(n)，其中n是链表的长度。逆置链表在实际应用
中有着广泛的用途，例如链表的搜索、排序和删除等操作。因此，
掌握单链表的逆置算法对于程序员来说是非常重要的。希望本文对
您有所帮助！
版权声明：本文标题：单链表的逆置c语言算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1713662521a645925.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论