对于不带头结点的单链表l,设计一个递归算法逆置所有结点。编写完整的实验程序,并采用相应数据进行测试。
时间: 2023-04-27 20:03:19 浏览: 402
给定一个不带头结点的单链表,写出将链表倒置的算法
5星 · 资源好评率100%
递归算法逆置单链表的思路如下:
1. 如果链表为空或只有一个结点,则无需逆置,直接返回原链表。
2. 否则,先递归逆置除第一个结点以外的所有结点,得到一个新的链表。
3. 然后将原链表的第一个结点插入到新链表的末尾,即可得到逆置后的链表。
下面是完整的实验程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结构体
typedef struct node {
int data;
struct node *next;
} Node;
// 创建单链表
Node *createList(int n) {
Node *head = NULL, *tail = NULL;
for (int i = ; i < n; i++) {
Node *p = (Node *)malloc(sizeof(Node));
p->data = i + 1;
p->next = NULL;
if (head == NULL) {
head = tail = p;
} else {
tail->next = p;
tail = p;
}
}
return head;
}
// 输出单链表
void printList(Node *head) {
for (Node *p = head; p != NULL; p = p->next) {
printf("%d ", p->data);
}
printf("\n");
}
// 递归逆置单链表
Node *reverseList(Node *head) {
if (head == NULL || head->next == NULL) {
return head;
}
Node *newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
int main() {
int n = 5;
Node *head = createList(n);
printf("原链表:");
printList(head);
head = reverseList(head);
printf("逆置后的链表:");
printList(head);
return ;
}
```
测试结果如下:
```
原链表:1 2 3 4 5
逆置后的链表:5 4 3 2 1
```
阅读全文