今天我们来讨论一下如何将两个链表合并的问题。
我们来看一下问题的具体描述：有两个单向链表，它们每个节点都有一个数字，且节点中的数字按照升序排列，现在需要合并这两个链表，合并后仍然是按照升序排列。
举例如下：
我们最先想到的应该是会用暴力方法来解决这个问题，即将直接将L2链表连接到L1链表后，形成新的链表，然后对新的链表进行排序。
虽然这个方法是可行的，但是这个方法并不是最好的，这个方法主要的耗时在于重新排序，它的时间复杂度是O（m+n）log（m+n），m和n分别是L1和L2链表的长度，稍后我们会给出更加优雅的方案以供讨论。
在提出第二种方案之前，需要提一下可能会用到的一个“工具”——虚拟节点（dummy node），虚拟节点是当我们合并两个链表时不知道哪个节点是新链表节点的头节点时会用到。对于我们之前提到的这个问题，我们会用到两个指针p1（指向L1头节点）、p2（指向L2头节点），前面提到的虚拟节点和当前节点（current node，用于循环，被初始化指向虚拟节点）。通过循环访问所有节点来构成新的链表。在每次循环中，会比较两个链表中p1和p2指向的节点的值，使当前节点一直指向较小值节点的下一节点。如下图：
在第一步中，p1指向的节点值为2，p2指向节点值为6,2小于6，所以curr指向p1，p1指向下一节点，即指向节点值为5的节点，如下图：
第二步中，p1指向的节点的值仍然小于p2指向的节点的值，所以继续向后移动，如下图：
第三步中，p1指向的节点的值大于p2指向的节点的值，curr指向p2当前指向的节点，p2向后移动，如下图：
以此类推，直到p1或者p2指针移动到链表的末端，因为我们在每次比较中都选择较小的值，所以当p1或者p2中任何一个指针指向链表末端，代表另外一个没有还没到达末端的链表的后序的值都比已到达末端的链表中最大的值要大，所以只需要将后续的节点追加到新的链表后即可。代码如下：
接下来我们介绍一下第三种方法，就是用递归的方式解决这个问题。递归（recursion）是一种在计算机科学中非常基本且普遍的思考问题的方式。典型的递归思路就是可以把问题变为更小的问题，并且这个更小的问题可以继续递归成更小的问题，知道这个问题小到到达一个边界条件（boundary condition），以至于可以很轻松地解决。
在这个问题中，我们的边界条件很简单，就是当L2指向了null，返回L1或者L1指向了null，返回L2。如果L1或者L2没有指向null，就需要比较L1和L2对应的值哪个更小，当有结果以后，这个新的链表就更长了，而需要比较的链表就更短了，显然，这样这个问题就比较之前的简单了，如此反复递归即可。代码如下：
为你详细讲解十二个常见算法问题，不仅让你学会如何掌握这些问题的解题代码，还会让你学到解决算法问题所必需的四类解题模板，让你轻松应对各类新问题。↓↓↓
继续阅读
阅读原文