链表中插入一个节点

node

*insert(node

*head,node

*p)

//

结点也要传指针

node

*p

{

node

*p1,*p2

if(head->data>=p->data){

p->next=head

head=p

return(head)}

p2=p1=head

while(p2->next&&p2->data<p->data)//循环结束的条件是p2指向尾结点或找到不小于

p

中数据的结点。

{

p1=p2

p2=p2->next

}

//此时，p2已经指向要插入的位置，只需将p结点插入到p2之后即可。

//if(p2->data<p-data){

无需此判断了。

p2->next=p

p->next=p2->next}

//改为这样。这里不是

判断表

尾，是插入p结点。

/*else{

同样无必要。

p->next=p2

p1->next=p

}

*/

return(head)

}

在单链表中插入新节点的算法思想是：

1.创建一个新节点，包含要插入的数据。

2.从链表的头部开始遍历链表，找到要插入位置的前一个节点。

3.将新节点的 next 指针指向前一个节点的 next 指针所指向的节点。

4.将前一个节点的 next 指针指向新节点。

下面是用 Java 实现的代码:

因为前面的语句是

while((new->num>p->num)&&(p->next!=NULL))

{

q=p

p=p->next

}

也就是如果新节点的值大于p所指的值并且p->next不为空，才会 *** 作q=p,p=p->next，这个过程是为了将p不断后移直到新节点的值不大于p或者是到了链表尾部，目的是找到q<new<=p（值域比较）的位置来插入new节点（即有序插入）。

之后if(new->num<=p->num)表明新节点的值不大于p->num，下面的 *** 作就是将节点插入到p节点之前；后面的else则表面是因为p->next等于NULL退出，也就是新节点的值比链表所有值都大，所以插入了尾部。

---