insert.h

南京航空航天大学王珊珊出版的C++详细课后习题程序集和PPT课件.

node *Insert(node *head,  node *p) 
{       // 把结点p插入到链表head中，使链表仍然保持升序
	node *p1, *p2;
	if(head==NULL) //如果插入前（原始链表）为空链表
	{
		head=p;
		p->next=NULL;
		return(head);
	}
	if( head->data >= p->data ) //插在链表首部
	{	
		p->next = head;
		head = p;
		return(head);
	}
	p2=p1=head; // 插在链表中间或尾部
	while( p2->next && (p2->data) < (p->data ) ) //查找待插入位置
	{	p1=p2; p2 = p2->next;  }
	if( (p2->data) < (p->data) ) // 插在链表尾部
	{	
		p2->next = p;
		p->next = NULL;
	}
	else //插在链表中间, p2之前
	{	
		p->next = p2;
		p1->next = p;
	}
	return(head);
}