C语言将一个带头结点的数据域依次为 a1,a2,…,an(n≥3)的单链表的所有结点逆置,即第一个 结点的数据域变为 an,…,最后一个结点的数据域为 a1。编程实现以上功能要求
时间: 2024-03-05 19:48:56 浏览: 82
可以按照以下步骤来实现单链表的逆置:
1. 遍历链表,统计链表的长度 n,并记录链表的尾节点。
2. 新建一个空节点,作为逆置后的链表的头结点。
3. 从头结点开始遍历原链表,依次将每个节点插入到新链表的头部。
4. 将新链表的头结点指向最后一个节点,将原链表的尾节点指向空节点。
下面是具体的 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=0; i<n; i++) {
LinkList p = (LinkList)malloc(sizeof(Node));
scanf("%d", &p->data);
p->next = NULL;
tail->next = p;
tail = p;
}
return head;
}
//逆置单链表
LinkList reverseList(LinkList head) {
LinkList p = head->next;
LinkList newHead = (LinkList)malloc(sizeof(Node));
newHead->next = NULL;
while(p) {
LinkList q = p->next;
p->next = newHead->next;
newHead->next = p;
p = q;
}
head->next = newHead->next;
return head;
}
//遍历单链表
void traverseList(LinkList head) {
LinkList p = head->next;
while(p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n;
printf("请输入单链表的长度:");
scanf("%d", &n);
LinkList head = createList(n);
printf("原链表为:");
traverseList(head);
head = reverseList(head);
printf("逆置后的链表为:");
traverseList(head);
return 0;
}
```
运行结果如下:
```
请输入单链表的长度:5
1 2 3 4 5
原链表为:1 2 3 4 5
逆置后的链表为:5 4 3 2 1
```
阅读全文