这是《剑指Offer》的第二十五题：

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 struct ListNode { int m_nKey; ListNode *m_pNext; };

这个题，我们还是和之前几篇文章一样，介绍两种方法，一种是自己想出来的常规解法，属于自下而上；另一种 是书中的解法，属于自上而下。我们先来说自己的解法。

对于这道题，我想的是，现在有两个链表 l1 和 l2，我们可以以 l1 作为基础链表，将 l2 插入的 l1 中去。 对于 l2 的每一个节点，我们在 l1 中找一个大于它的节点，然后把 l2 的这个节点插入到它后面。这里，我们 把找到的 l1 节点记为 node1，node1 前的一个节点记为 preNode1，找到的 l2 节点记为 node2，那么我们根据 node1 在 l1 中的位置可以把情况 分为：

  • 当 node1 为头节点时，那么说明 l1 的所有节点都要比 node2 大，所以应该把 node2 变成 l1 的头节点
  • 当 node1 为中间节点时，我们应该把 node2 插入到 node1 前面，preNode1 向前移动指向 node2
  • 当 node1 为尾节点时，因为我们是向 node1 前面插入节点，所以和 node1 为中间节点时操作一样
  • 当 l1 中没有大于 node2 时，说明 l1 的所有节点都要比 node2 小，所以应该把 l1 的最后一个节点的 m_pNext 指向 node2，然后返回 l1

你看，这样问题就解决了。虽然以上算法描述中有两层循环，外层循环是 l2，内层循环是 l1，但是总的时间复杂度 却还是线性的，为 O(len(l1) + len(l2))，没有使用多余的空间，所以空间复杂度为 O(1)。

这是我的提交记录。

说完了我的解法，我们现来看看书中的解法。书中解法是递归形式的。核心思想在于，不断的去找头节点。比如我们现在 有两个节点，node1 指向 l1 的节点，node2 指向 l2 的节点，如果 node1->m_nKey > node2->m_nKey，那么 node2 就应该是 合并之后链表的头节点。之后，我们不断递归重复调用这个过程。

这是我用书中的解法重新提交的代码。

哇，当时我一读完，觉得这思路太厉害了。我在一开始也想过用递归去分析问题，但是想来想去，也没有想到合适的 思路。可见自己的递归功力还是差的很多呀。于是自己赶紧记录下来，希望自己以后面对问题也能有这样清晰的思路。

以上。