题目(合并两个排序的链表)

输入两个递增排序的链表，合并这两个链表并使得新链表中的节点仍然是递增排序的。

算法思路

首先应考虑代码鲁棒性，如果输入的链表 1 为空，那么链表 2 就是合并链表；如果输入的链表 2 为空，那么链表 1 就是合并的链表。

非递归版本

首先应该先确定合并链表的头结点,由指针 mergedHead 表示。然后定义合并链表的工作指针 p(初始指向头结点) 来完成合并链表的连接工作。

那么有了合并链表的工作指针 p，我们只要确定连接到 p 的下一个节点就行。因此只需要比较链表 1 和链表 2 的工作指针所指向的节点大小即可。那么重复以上操作，循环条件为链表 1 和链表 2 不空。

最后一步还需要检查是否还有剩余节点未完全连接完，因此需要对链表 1 或链表 2 判空，若有剩余节点，择全部连接到工作指针 p 的后面即可，最后的最后将合并链表的尾节点指针置空。

递归版本

递归版本只要一个表示合并链表的头指针，然后依次递归比较两个链表中对应位置上节点的大小，然后递归连接到合并链表的指针上去即可。这里不再需要一个合并链表的工作指针，合并链表的指针自己就可以完成连接工作，它的下一个节点都是递归返回的。需要注意的是，递归版本没有移动这个指针，非递归版本中需要移动这个指针，因此设置了一个工作指针 p 代替合并链表指针来移动，原因在于我们最终返回的是合并链表的头结点指针，所以不能移动它，而所以就利用工作指针来移动并完成连接操作。

算法实现

非递归版本

复杂度分析

假设链表 1 有 m 个节点，链表 2 有 n 个节点。对非递归版本，算法需要遍历两个链表的节点，因此时间复杂度为 O(m+n)，算法仅改变指针指向，没有消耗额外空间，空间复杂度为 O(1)；对递归版本，时间复杂度相同，但由于使用递归，需要消耗递归工作栈，因此空间复杂度为 O(min(m,n))。

参考

<<剑指offer2>>