在单链表中，在偶数位插入新节点？写出算法思想以及相应的代码？

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

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

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

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

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

下面是用 Java 实现的代码:

单向链表的插入图示：

---->[NULL]（原链表）

head

---->[1]---->[NULL]（插入后的链表）

head 1->next

图7 空链表插入一个节点

结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：

1、你要明白空链表head指向NULL就是head=NULL；

2、插入后head指向第1个节点，就是让head=1,1->next=NULL,OK这样就行了。

---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）

head 1->next 2->next 3->next n->next

---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的链表）

head 1->next 2->next x->next 3->next n->next

图8：有N个节点的链表，插入一个节点（这里图示插入第2个后面）

结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：

1、你要明白原1->next就是节点2，2->next就是节点3；

2、插入后x指向第3个节点,2指向x，就是让x->next=2->next,1->next=x。

*/

struct Node *Insert(struct Node *head, long num, struct Node *node)

{

struct Node *p1 /*p1保存当前需要检查的节点的地址*/

if (head == NULL) /*（结合图示7理解）*/

{

head = node

node->next = NULL

n += 1

return head

}

p1 = head

while (p1->num != num &&p1->next != NULL) /*p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找*/

{

p1 = p1->next/*后移一个节点*/

}

if (num == p1->num) /*找到了（结合图示8理解）*/

{

node->next = p1->next/*显然node的下一节点是原p1的next*/

p1->next = node/*插入后，原p1的下一节点就是要插入的node*/

n += 1/*节点总数增加1个*/

}

else

{

printf(" %ld not been found! ",num)

}

return head

}

student *add(student *head)

{

student *p=new student,*p1, *p2

cin>>p->num>>p->name>>p->eng>>p->math>>p->c

if (head == NULL) // 检查头指针是否为空, 是直接赋值

head = p

else// 否, 则遍历链表找到合适的位置插入新节点

{

p1 = head

while(p1!=NULL)

{

p2 = p1 // 保存当前节点

p1=p1->next // 进入下个节点

}

p1=p // 存储新节点

p2->next=p1 // 将新节点赋值到链尾

}

return head

}

---