题目来源：
21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (NULL == list1) return list2; if (NULL == list2) return list1; struct ListNode* head = NULL, * tail = NULL; while (list1 && list2)//有一个为空就跳出，后面直接把不为空的接上就可以 { //尾插 if (list1->val < list2->val) { if (NULL == tail) { head = tail = list1; } else { tail->next = list1; tail = tail->next; } list1 = list1->next; } else { if (NULL == tail) { head = tail = list2; } else { tail->next = list2; tail = tail->next; } list2 = list2->next; } } if (NULL == list1)//list1为空，直接把list2接在后面 tail->next = list2; else tail->next = list1; return head; }
思路分析：
为实现本题，我们要创建两个结构体指针，head 和 tail ，都初始化为NULL。我们的思路是对比两个链表的每个结点，将小的进行尾插。
实现过程：
我们先处理特殊情况，如果 list1 或者 list2 某一个为空，那就返回另一个。
if (NULL == list1) return list2; if (NULL == list2) return list1;
1.比较 list1->val 与 list2->val，如果 list1->val 小，那就将 list1 作为新的头结点，让 head与tail 都赋值为 list1，插入后就让 list1 往后走一步。如果比较是相反的结果，那就将 list2 赋给 head与tail，list2 作为合成的头结点；
2.在比较新的 list1->val 与 list2->val 时，如果 list2->val 小，那就开始尾插，将 list2 赋给 tail->next，更新 tail，并更新 list2，让 list2 往后走一步。如果比较的结果相反，那就将 list1 赋给 tail->next，更新 tail 与 list1；
3. 循环步骤 1与2，当 list1/list2 任一走到空，就把不为空的那个链表直接接在 tail->next 上，并返回合成后的链表头 head。
*** 本篇结束 ***
