21、合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2： 

输入：l1 = [ ], l2 = [ ]
输出：[ ]

示例3： 

输入：l1 = [ ], l2 = [0]
输出：[0]

struct ListNode {
      int val;
      struct ListNode *next;
  };

解题思路： 

1、先考虑list1和list2可能为空的情况

2、使用dummy->next来保存需要返回的头节点

3、判断 list1 和 list2 哪个更小，就把这个节点接到下一个

使用指向指针的指针 cur 用来存储更小的一边的指针

在帮助 dummy 连接之后，还可以控制更小的 list1 或 list2 向后移动

4、直到有一边为NULL ，即可将另一边剩余的都接上

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  if(!list1 || !list2) return list1 ?list1 : list2;
  struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));//创建哨兵结点，给哨兵结点分配空间
  struct ListNode* cur = dummy;//创建临时指针，给临时指针赋初值
  while(list1&&list2)
  {
    if(list1->val<=list2->val)
    {
        cur->next=list1;//临时指针指向 list1
        cur=list1;//赋值
        list1=list1->next;
    }
     else
    {
        cur->next=list2;
        cur=list2;
        list2=list2->next;
    }
      }
//边界判断
  if(list1)
  cur->next=list1;
  if(list2)
  cur->next=list2;
    return dummy->next;//这里，dummy是哨兵，里面存的是 NULL，返回咱们自己设的这个哨兵没意义，所以返回 next
}