42 p = head2;
43 }
44 else
45 {
46 head = head2;
47 p = head1;
48 }
49
50 while(p != NULL)
51 {
52 nextP = p->next; //保存p的下一个节点
53 head = insert_node(head, p); //把p插入到目标链表中
54 p = nextP; //指向将要插入的下一个节点
55 }
56
57 return head;
58 }
这里insert_node()函数是有序的插入节点，注意与前面例题中的函数有区别，这里它传入的参数是node*类型。然后在merge()函数中（代码52~55行）循环把短链表中的所有节点插入到长链表中。
接下来介绍非递归方法。比如有下面两个链表：
链表1：1->3->5
链表2：2->4->6
递归方法的步骤如下：
（1）比较链表1和链表2的第一个节点数据，由于1<2，因此把结果链表头节点指向链表1中的第一个节点，即数据1所在的节点。
（2）对剩余的链表1（3->5）和链表2再调用本过程，比较得到结果链表的第二个节点，即2与3比较得到2。此时合并后的链表节点为1->2。
接下来的过程类似（2），如此递归知道两个链表的节点都被加到结果链表中。
1 node * MergeRecursive(node *head1, node *head2)
2 {
3 node *head = NULL;
4
5 if (head1 == NULL)
6 {
8 }
9 if (head2 == NUL)
10 {
11 return head1;
12 }
13
14 if ( head1->data < head2->data )
15 {
16 head = head1 ;
17 head->next = MergeRecursive(head1->next,head2);
18 }
19 else
20 {
21 head = head2 ;
22 head->next = MergeRecursive(head1,head2->next);
23 }
24
25 return head ;
26 }
下面是测试程序：
1 int main()
2 {
3 node *head1 = create(); //创建单链表1
4 node *head2 = create(); //创建单链表2
5 //node *head = merge(head1, head2);
6 node *head = MergeRecursive(head1, head2);
7 print(head);
8
9 return 0;
10 }
这里使用merge()函数和MergeRecursive()函数测试，结果一致。
作者“志在千里”