0021.md

• 如果一个链表为空，直接返回另一个即可。如果两个链表都不为空，比较两个头节点大小，小的作为合并后的头节点。合并剩余元素，将合并结果链接到合并的头节点之后

class Solution {
 public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) {
      return l2;
    }
    if (!l2) {
      return l1;
    }
    if (l1->val < l2->val) {
      l1->next = mergeTwoLists(l1->next, l2);
      return l1;
    }
    l2->next = mergeTwoLists(l2->next, l1);
    return l2;
  }
};

• 以 124 和 134 两个链表为例

l1 = 1->2->4
l2 = 1->3->4

res = 1
l1 = 1->2->4
l2 = 3->4

res = 1->1
l1 = 2->4
l2 = 3->4

res = 1->1->2
l1 = 4
l2 = 3->4

res = 1->1->2->3
l1 = 4
l2 = 4

res = 1->1->2->3->4
l1 = 4
l2 = null

res = 1->1->2->3->4->4
l1 = null
l2 = null

实际执行过程为：
res = 4
res = 4->4
res = 3->4->4
res = 2->3->4->4
res = 1->2->3->4->4
res = 1->1->2->3->4->4