单链表逆置算法
/*Name: 单链表逆置
Copyright:
Author: 巧若拙
Date: 22-11-14 16:13
Description:
分别用递归和非递归两种方式实现单链表(不含头结点)的逆置
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef char ElemType;
typedef int Status; //函数类型,其值是函数结果状态代码,如OK等
typedef struct Node{
ElemType data;//数据域
struct Node *next;//指针域
} Node, *LinkList;
void CreatList(LinkList *head);//创建一个不带头结点的单链表
void DisplayList(LinkList head);//输出单链表的所有结点
void ReverseList(LinkList *head);//逆置单链表方法1
LinkList ReverseList_2(LinkList head);//逆置单链表方法2
LinkList ReverseList_3(LinkList head, Node *pre);//逆置单链表方法3(递归),确保head非空
int main(void)
{
LinkList a = NULL;
CreatList(&a);//创建一个不带头结点的单链表
DisplayList(a);//输出单链表的所有结点
ReverseList_1(&a);//逆置单链表方法1
DisplayList(a);//输出单链表的所有结点
a = ReverseList_2(a);//逆置单链表方法2
DisplayList(a);//输出单链表的所有结点
a = ReverseList_3(a, NULL);//逆置单链表方法2
DisplayList(a);//输出单链表的所有结点
return 0;
}
void CreatList(LinkList *head)//创建一个不带头结点的单链表
{
int i;
Node *p, *s;
//创建第一个结点
*head = (LinkList)malloc(sizeof(Node));
if (!*head)
{
printf("Out of space!");
exit(0);
}
p = *head;
p->data = 'A';
p->next = NULL;
for (i=1; i<10; i++)//创建其余的结点
{
s = (LinkList)malloc(sizeof(Node));
if (!s)
{
printf("Out of space!");
exit(0);
}
s->data = i + 'A';
s->next = NULL;
p->next = s;
p = p->next;
}
}
void DisplayList(LinkList head)//输出单链表的所有结点
{
while (head)
{
printf("%c ", head->data);
head = head->next;
}
printf("\n");
}
void ReverseList_1(LinkList *head)//逆置单链表方法1
{
Node *left, *mid, *right;
left = *head;
mid = left->next;
left->next = NULL;
while (mid)
{
right = mid->next;
mid->next = left;
left = mid;
mid = right;
}
*head = left;
}
LinkList ReverseList_2(LinkList head)//逆置单链表方法2
{
Node *left, *mid, *right;
left = head;
mid = left->next;
left->next = NULL;
while (mid)
{
right = mid->next;
mid->next = left;
left = mid;
mid = right;
}
return left;
}
LinkList ReverseList_3(LinkList head, Node *pre)//逆置单链表方法3(递归),确保head非空
{
Node *p = head->next;
head->next = pre; //逆置尾指针
return p ? ReverseList_3(p, head) : head;
}