【数据结构】合并两个有序链表

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

Definition for singly-linked list.
  struct ListNode {
      int val;
      struct ListNode *next;
  };

 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
     if(list1 ==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    ListNode* l1=list1;
    ListNode* l2=list2;

    //创建新链表
    ListNode* listhead;
    ListNode* listtail;
    listhead=listtail=NULL;
   
    while(l1 && l2)
    {
        //l1大
        if(l1->val > l2->val)
        {
            //为空
            if(listhead==NULL)
            {
                listhead=listtail=l2;
            }else{
                //不为空 尾插
                listtail->next=l2;
                listtail=listtail->next;
            }
            l2=l2->next;
        }else{
            //l2大
            //为空
            if(listhead == NULL)
            {
                listhead=listtail=l1;
            }else{
                //不为空
                listtail->next=l1;
                listtail=listtail->next;
            }
            l1=l1->next;
        }
    }
    if(l1)
    {
        listtail->next=l1;
    }
    if(l2)
    {
        listtail->next=l2;
    }

    return listhead;
}

大框架就是把从小到大的依次放进新链表中。
先是判断一下如果链表1是空的话就直接返回链表2。如果链表2是空的话就直接返回链表1。然后创建新链表其实也可以先创建新链表在判断是否有空链表。

接下来就要比较了，用while循环判断条件是链表1和链表2（l1和l2）都不能为空。

在l1的值大于l2的值的情况下，因为是升序链表所以要先把小的放入链表中，如果新链表为空就把l2放入新链表中，如果新链表不为空就尾插。在l2大于l1的情况下，重复上面的步骤。注意在这之中不要忘了让节点的指针往后走。

像这种情况一个链表走完了，另一个链表还没有走完。我们就要判断了，如果l1不为空就把l1尾插，如果l2不为空就把l2尾插。