题目：

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解题思路：

1.合并就是改变表的next的指针，根据升序将两个升序表重新链接即可；
2.最后返回初始地址的指针就可以了。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  12.         //new_one实时指针，first指向新链表的初始地址
  13.         ListNode* new_one = NULL;
  14.         ListNode* first = NULL;
  16.         //检测空指针
  17.         if(l1 == NULL){
  18.             return l2;
  19.         }
  20.         if(l2 == NULL){
  21.             return l1;
  22.         }
  24.         //首地址传值，与后面的使用new_one->next不同
  25.         //确定first
  26.         if(l1->val < l2->val){
  27.             new_one = l1;
  28.             l1 = l1->next;
  29.         }
  30.         else{
  31.             new_one = l2;
  32.             l2 = l2->next;
  33.         }
  34.         first = new_one;
  36.         //链表重新链接
  37.         for(;l1 != NULL && l2 != NULL;){
  38.             if(l1->val < l2->val){
  39.                 new_one->next = l1;
  40.                 new_one = new_one->next;
  41.                 l1 = l1->next;
  42.             }
  43.             else{
  44.                 new_one->next = l2;
  45.                 new_one = new_one->next;
  46.                 l2 = l2->next;
  47.             }
  48.         }
  50.         //末尾处理
  51.         if(l1 == NULL){
  52.             new_one->next = l2;
  53.         }
  54.         else{
  55.             new_one->next = l1;
  56.         }
  59.         return first;
  60.     }
  61. };

思考：

1.指针使用前必须进行检测是否为空指针；

出现如下报错：Line 17: Char 16: runtime error: member access within null pointer of type ‘ListNode’ (solution.cpp)
错误原因：试图使用空指针
image.png这个原先没有加。
**

2.0ms代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. // 迭代的方法很有意思
  10. class Solution {
  11. public:
  12.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  13.         if (l1 == NULL) return l2;
  14.         else if (l2 == NULL) return l1;
  15.         else if (l1->val < l2->val) {
  16.             l1->next = mergeTwoLists(l1->next, l2);
  17.             return l1;
  18.         } else {
  19.             l2->next = mergeTwoLists(l1, l2->next);
  20.             return l2; 
  21.         }
  22.     }
  23. };

3.上述代码的改进在于使用函数递归方式来完成，不用记录初始指针，不用对首尾情况进行分别讨论。