1.9 如何合并两个有序链表

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

已知两个链表head1和head2 各自有序（例如升序排列），请把它们合并成一个链表，要求合并后的链表依然有序。

分析与解答：

分别用指针head1和head2来遍历两个链表，如果当前head1指向的数据小于head2指向的数据，则将head1指向的结点归入合并后的链表中，否则，将head2指向的结点归入合并后的链表中。如果有一个链表遍历结束，则把未结束的链表连接到合并后的链表尾部。

下图以一个简单的示例为例介绍合并的具体方法：

由于链表按升序排列，首先通过比较链表第一个结点中元素的大小来确定最终合并后链表的头结点；接下来每次都找两个链表中剩余结点的最小值链接到被合并的链表后面，如上图中的虚线所示。在实现的时候需要注意，要释放head2链表的头结点，实现代码如下：

程序的运行结果为

算法性能分析：

以上这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。