合并两个有序链表_struct listnode *mergetwolists1

题目链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

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

 思路：把list1 和list2 放到一个新链表里面，其中head为头，tail为尾，是新链表的指针，每次取小的节点尾插到新链表。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
      struct ListNode*head=NULL;
      struct ListNode *tail=NULL;
//list1和list2为空时
      if(list1==NULL){
          return list2;
      }
      if(list2==NULL){
          return list1;
      }
 
      while(list1 && list2){
         if(list1->val<list2->val){
             if(tail==NULL){
                 head =tail =list1;
                 
             }
             else{
                 tail->next=list1;
                 tail=list1;
             }
             list1=list1->next;
         }
         else{
             if(tail==NULL){
                 head =tail =list2;
    
             }
             else{
                 tail->next=list2;
                 tail=list2;
             }
             list2=list2->next;
         }
      }
//list1先为空时
      if(list1){
          tail->next=list1; 
      }
//list2先为空时
      if(list2){
          tail->next=list2;
      }
      return head;
}

还有可以用递归写

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1 == NULL)
        return list2;
    else if(list2 == NULL)
        return list1;
    else if(list1->val < list2->val)
    {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
    else
    {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}
 

但不推荐，容易栈溢出。