文章目录
- 一【题目类别】
- 二【题目来源】
- 三【题目描述】
- 四【解题思路】
- 五【时间频度】
- 六【代码实现】
- 七【程序测试】
一【题目类别】
二【题目来源】
- 本题目选自王道2023考研计算机数据结构复习指导40页中二、综合应用题之03题
三【题目描述】
- 设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
四【解题思路】
- 对于这种题，我们要有头插法和尾插法的算法基础，本题我们使用头插法，思路简单来说就是将待逆置的单链表，使用头插法插入到另一个单链表中，从而实现单链表的逆置，这样也就可以实现反向输出单链表元素的目的。另外对于初学者，需要注意指针的使用
五【时间频度】
- 时间复杂度：
O
(
n
)
O(n)
O(n)，其中
n
n
n为单链表长度
- 空间复杂度：
O
(
n
)
O(n)
O(n)
六【代码实现】
#define _CRT_SECURE_NO_WARNINGS
#include
#include
typedef struct LNode
{
int data;
struct LNode* next;
}Node,*Link;
void Reverse(Link link1, Link link2)
{
Node* p = link1;
while (p->next != NULL)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = p->next->data;
temp->next = link2->next;
link2->next = temp;
p = p->next;
}
}
void PrintLink_ReversePrint(Link link)
{
Node* p = link->next;
while (p != NULL)
{
if (p->next != NULL)
{
printf("%d->", p->data);
}
else
{
printf("%d", p->data);
}
p = p->next;
}
}
int main()
{
Link link1 = (Link)malloc(sizeof(Node));
link1->next = NULL;
Link link2 = (Link)malloc(sizeof(Node));
link2->next = NULL;
Node* p = link1;
int len;
printf("请输入单链表的长度：");
scanf("%d", &len);
printf("请输入单链表的元素：");
for (int i = 0; i < len; i++)
{
int x;
scanf("%d", &x);
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = x;
temp->next = NULL;
p->next = temp;
p = temp;
}
Reverse(link1, link2);
printf("初始单链表为：");
PrintLink_ReversePrint(link1);
printf("n");
printf("逆置后的单链表为：");
PrintLink_ReversePrint(link2);
printf("n");
system("pause");
return 0;
}
七【程序测试】
