头插法

定义：输入的数据次序生成的链表节点次序相反，例如：按1,2,3顺序进行头插之后，最终排序却变成了3,2,1。简而言之就是逆序插入。
定义图解：

代码图解：

代码：（使用头插法建立单链表）

Linklist head_insert(Linklist &L){
	//准备工作
	LNode *s; // s是指向待插入结点的指针
	int x; // 传入结点中data的值
	L=(Linklist*)malloc(sizeof(LNode)); 
	// ❤创建L链表,
	//malloc()函数为动态申请空间
	//(Linklist*)为强制转化为Linklist类型
	L->next=NULL; // L链表的头结点置空
	scanf("%d",&x);
	//以下核❤
	while(x!=NULL){ // 输入的值不为空，就可以进行头插了
		s=(LNode*)malloc(sizeof(LNode)); // 题目没给结点，所以需要申请
		s->data=x; // s是个指针，需要指向一个值才能进行头插
		s->next=L->next; // 头插法核❤
		L->next=s;
		scanf("%d",&x);
	}
	return L; // 头插完成，返回最终的L链表
}

小结：头插通常应用于逆置。
头插防断链，如何理解？
分析：如图所示，若要将链表B头插进链表A中，此时p->next更改为A->next了，如果没有r指针，当头插完p当前所指结点后，B链表就断了，那么就无法将剩下的B链表结点插入到A链表中了，所以需要一个r指针，始终指向p的下一个结点，即r=p->next。
代码图解：