合并

考点：单链表的操作
出现频率：★★★★
已知两个链表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                       head = head1;
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                {
7                         return head2;
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()函数测试，结果一致。