数据结构之单链表的创建和逆转

一、单链表的创建

• 前插法（头插法）
• 后插法

二、单链表的逆转

一、单链表的创建

1.前插法：

思路：总将新节点插到链表前端，成为首元节点。

typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode* next; //结点的指针域
} LNode, * LinkList; //LinkList为指向结构体LNode的指针类型

void create_list_h(LinkList &L,int n)
{
	L=new LNode;
	L->next=NULL;//建立带头结点的单链表
	for(int i=n;i>0;i--)
	{
		LinkList p=new LNode;//生成新结点
		cin>>p->data;//输入元素值
		p->next=L->next;
		L->next=p;//插入到表头
	}
}

2.后插法：

思路：总将节点插到链表的尾部

typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode* next; //结点的指针域
} LNode, * LinkList; //LinkList为指向结构体LNode的指针类型

void create_list_r(LinkList &L,int n)
{
	L=new LNode;
	L->next=NULL;
	LinkList P=L;//尾指针指向头节点
	for(int i=0;i<n;i++)
	{
		LinkList q=new LNode;
		cin>>q->data;
		q->next=NULL;
		P->next=q;//插入到表尾
		P=q;//q指向新的尾节点	
	}
}

二、单链表的逆转

思路：先把链表一分为二，再利用前插法逐一接到头结点处。

typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode* next; //结点的指针域
} LNode, * LinkList; //LinkList为指向结构体LNode的指针类型

void list_inverse(LinkList &L)
{
	LinkList P,q;
	P=L->next;
	L->next=NULL;
	//将链表一分为二
	while(P)
	{
		q=P->next;//q指向*p的后继节点；
		P->next=L->next;
		L->next=P;//*p插在头节点后
		P=q;
	}
}