6
7 node* InsertSort(void)
8 {
9 int data = 0;
10 struct node *head=NULL,*New,*Cur,*Pre;
11 while(1)
12 {
13 printf("please input the data\n");
14 scanf("%d", &data);
15 if (data == 0) //输入0结束
16 {
17 break;
18 }
19 New=(struct node*)malloc(sizeof(struct node));
20 New->data = data; //新分配一个node节点
21 New->next = NULL;
22 if(head == NULL)
23 { //第一次循环时对头节点赋值
24 head=New;
25 continue;
26 }
27 if(New->data <= head->data)
28 {//head之前插入节点
29 New->next = head;
30 head = New;
31 continue;
32 }
33 Cur = head;
34 while(New->data > Cur->data && //找到需要插入的位置
35 Cur->next!=NULL)
36 {
37 Pre = Cur;
38 Cur = Cur->next;
39 }
40 if(Cur->data >= New->data) //位置在中间
41 { //把new节点插入到Pre和cur之间
42 Pre->next = New;
43 New->next = Cur;
44 }
45 else //位置在末尾
46 Cur->next = New; //把new节点插入到cur之后
47 }
48 return head;
49 }
已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。使用非递归方法以及递归方法。
解析：
首先介绍非递归方法。因为两个链表head1 和head2都是有序的，所以我们只需要找把较短链表的各个元素有序的插入到较长的链表之中就可以了。
源代码如下：
1 node* insert_node(node *head, node *item) //head != NULL
2 {
3 node *p = head;
4 node *q = NULL; //始终指向p之前的节点
5
6 while(p->data < item->data && p != NULL)
7 {
8 q = p;
9 p = p->next;
10 }
11 if (p == head) //插入到原头节点之前
12 {
13 item->next = p;
14 return item;
15 }
16 //插入到q与p之间之间
17 q->next = item;
18 item->next = p;
19 return head;
20 }
21
22 /* 两个有序链表进行合并 */
23 node* merge(node* head1, node* head2)
24 {
25 node* head; //合并后的头指针
26 node *p;
27 node *nextP; //指向p之后
28
29 if ( head1 == NULL ) //有一个链表为空的情况，直接返回另一个链表
30 {
31 return head2;
32 }
33 else if ( head2 == NULL )
34 {
35 return head1;
36 }
37
38 // 两个链表都不为空
39 if(length(head1) >= length(head2)) //选取较短的链表
40 { //这样进行的插入次数要少些
41 h