针对线性表的单链表存储结构,编写算法实现逆置的完整代码
时间: 2023-06-17 22:05:50 浏览: 109
下面是基于单链表存储结构的逆置算法的完整代码,其中假设链表已经存在并且头结点为 head:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 定义链表逆置函数
ListNode* reverseList(ListNode *head) {
ListNode *prev = NULL;
ListNode *curr = head;
ListNode *next;
while (curr != NULL) {
next = curr->next; // 保存当前节点的后继节点
curr->next = prev; // 当前节点指向它的前驱节点
prev = curr; // 将当前节点设为前驱节点
curr = next; // 将下一个节点设为当前节点
}
// 返回逆置后的链表头节点
return prev;
}
int main() {
// 创建链表
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->val = 1;
ListNode *node1 = (ListNode*)malloc(sizeof(ListNode));
node1->val = 2;
ListNode *node2 = (ListNode*)malloc(sizeof(ListNode));
node2->val = 3;
head->next = node1;
node1->next = node2;
node2->next = NULL;
// 打印原链表
printf("原链表:");
ListNode *p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
// 逆置链表
ListNode *newHead = reverseList(head);
// 打印逆置后的链表
printf("逆置后的链表:");
p = newHead;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
return 0;
}
```
在这个代码中,我们定义了一个链表节点结构体 ListNode,其中包含一个整数值 val 和一个指向下一个节点的指针 next。在主函数中,我们创建了一个包含三个节点的链表,并打印出原链表。然后我们调用 reverseList() 函数逆置链表,并打印出逆置后的链表。最终的输出结果如下:
```
原链表:1 2 3
逆置后的链表:3 2 1
```
阅读全文