用C语言将一个带头结点的数据域依次为 a1,a2,…,an(n≥3)的单链表的所有结点逆置, 即第一个结点的数据域变为 an,…,最后一个结点的数据域为 a1。编程实现以上功能要求
时间: 2024-03-25 07:41:36 浏览: 79
以下是用C语言实现将单链表逆置的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkList;
LinkList createList(int n) {
LinkList head = (LinkList) malloc(sizeof(Node));
head->next = NULL;
LinkList tail = head;
for (int i = 1; i <= n; i++) {
LinkList p = (LinkList) malloc(sizeof(Node));
scanf("%d", &(p->data));
p->next = NULL;
tail->next = p;
tail = p;
}
return head;
}
void printList(LinkList head) {
LinkList p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void reverseList(LinkList head) {
if (head->next == NULL || head->next->next == NULL) {
return;
}
LinkList pre = NULL, cur = head->next, next = cur->next;
while (cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head->next = pre;
}
int main() {
int n;
printf("请输入链表长度:");
scanf("%d", &n);
LinkList head = createList(n);
printf("原链表:");
printList(head);
reverseList(head);
printf("逆置后的链表:");
printList(head);
return 0;
}
```
上述代码中,我们定义了一个 `Node` 结构体,表示链表中的一个结点,结构体中包括一个 `data` 成员表示结点的数据,和一个 `next` 成员表示下一个结点的指针;同时定义了一个 `LinkList` 类型,表示链表的头指针。
在 `createList` 函数中,我们根据输入的参数 `n`,动态分配 `n` 个结点,并将它们按照输入顺序连接成一个带头结点的单向链表。在 `printList` 函数中,我们遍历链表并输出每个结点的数据值。
在 `reverseList` 函数中,我们使用三个指针 `pre`、`cur` 和 `next` 分别表示当前结点、前一个结点和后一个结点。我们遍历链表,每次将当前结点的指针指向前一个结点,然后将三个指针依次向后移动一个位置。最后,将头结点的指针指向链表的最后一个结点,即完成了链表的逆置。
在 `main` 函数中,我们先输入链表长度和每个结点的数据值,然后创建链表并输出原链表。接着调用 `reverseList` 函数将链表逆置,并输出逆置后的链表。
阅读全文