今天有童鞋在群里问怎么合并两个有序链表。尝试写了一下，
递归方式比较直观而且不容易出错，非递归的话代码可读性差一点而且也容易写错。这里提供一下主要代码。
注意：如果是双向链表会更加复杂需要同时维护每个节点的两个指针，为了避免出错。双向链表强力建议增加头尾的哨兵节点。
定义一个链表的节点如下：
template <typename Comparable>
struct Node {Comparable element;Node * next;Node(const Comparable &e, Node *n = nullptr): element{ e }, next{ n }{}
};采用递归方式合并
template <typename Comparable>
Node<Comparable> *
merge(Node<Comparable> * n1, Node<Comparable> * n2);/**
* assume n1 < n2
*/
template <typename Comparable>
Node<Comparable> *
merge1(Node<Comparable> * n1, Node<Comparable> * n2)
{if (n1->next == nullptr)n1->next = n2;else {n1->next = merge(n1->next, n2);}return n1;
}template <typename Comparable>
Node<Comparable> *
merge(Node<Comparable> * n1, Node