对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，

Question

对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。
typedef struct node
{int data; struct node *next;
}linknode,*link;
void Insertsort(link L)
{ link p,q,r,u;
p=L->next; (1)______;
while((2)________)
{ r=L; q=L->next;
while((3)________&& q->data<=p->data) {r=q; q=q->next;}
u=p->next; (4)______; (5)______; p=u;
}
}

Answer 1

(1) L->next=NULL
(2) p (或p!=NULL)
(3) q (或q!=NULL)
(4) p->next=r->next
(5) r->next=p // (4) 和 (5)是将p结点插入到 r 结点和q 结点之间

Answer 2

该题是用单链表来进行排序的操作，头结点中没有数据，数据从头结点后的第一个结点开始。P为遍历原链表的当前结点指针，r为已排序链表中查找插入位置的前指针，q为已排序链表中查找插入位置的后指针，u始终指向原链表中剩余部分的第一个结点。
(1)L->next=null，使该函数跳过第二个while，进行初始化
(2)p!=null，判断条件，p为空链表结束
(3)q!=null，判断条件，防溢出
(4)p->next=r->next，与第五步共同构成交换链表中不符合大小关系的两个数
(5)r->next=p