[数据结构与算法]链表直接插入排序

带头结点

基本思想：
将带头结点head的链表拆分为：head带一个结点的链表和q带剩余结点的链表，将q中的每个结点逐次插入到head链表中，构成一个带头结点且结点值递增的链表

关键代码：

LinkList sort(LinkList &head){
	LinkList p, q, r, l;
	p = head->next;//将原链表拆分为两个链表,一个head带一个结点,一个q带剩余结点 
	q = p->next;
	p->next = NULL;
	while(q!=NULL){
		p = head;
		r = q->next;
		while(p->next!=NULL){//找到要插入的位置 
			if(p->next->number<q->number){
				p=p->next;
			}else{
				break;
			}
		}
		q->next = p->next;//插入结点 
		p->next = q;
		q = r;//恢复位置 
		l = head;
		int i=0;
		printf("插入第%d个结点后，第一个链表为",++i);
		while(l!=NULL){
			printf(" %d", l->number);
			l = l->next;
		}
		printf("\n");
	}
	
	return head; 
}

不带头结点

基本思想：
将不带头结点head的链表拆分为：head指向的一个结点的链表和q带剩余结点的链表，将q中的每个结点逐次插入到head链表中，构成一个不带头结点结点值递增的链表

关键代码：

	LinkList Sort(LinkList &head){
	LinkList p, q, r, l;
	q = head->next;
	head->next = NULL;
	while(q!=NULL){
		p = head;
		r = q->next;
		if(q->number<p->number){//q插入head第一个结点之前 
			q->next = p;
		}else{//q大于等于head第一个结点,从head第二个结点开始比较 
			while(p->next!=NULL){//q插入head中间或最后 
				if(p->next->number<q->number){
					p=p->next;
				}else{
					break;
				}
			}
			q->next = p->next;
			p->next = q;
		}
		q = r;
		l = head;
		int i=0;
		printf("插入第%d个结点后，第一个链表为",++i);
		while(l!=NULL){
			printf(" %d", l->number);
			l = l->next;
		}
		printf("\n");
	}
	return head;
}