[数据结构与算法]leetcode---合并两个有序链表 21

leetcode—合并两个有序链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解法一： 合并的新链表是不具有哨兵结点的。

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


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    //定义头尾结点
   struct ListNode *head=NULL,*tail=NULL;
    //当两个链表有空链表的时候
   if(l1==NULL){
       return l2;
   }
   if(l2==NULL){
       return l1;
   }
   //定义合并链表的头和尾结点
   if(l1->val<l2->val){
       head=tail=l1;
       l1=l1->next;
   }
   else{
       head=tail=l2;
       l2=l2->next;
   }
   while(l1 && l2){
       if(l1->val<l2->val){
           tail->next=l1;
           tail=l1;
           l1=l1->next;
       }else{
           tail->next=l2;
           tail=l2;
           l2=l2->next;
       }
   }
   //当l1还有剩余的链表的时候
   if(l1){
       tail->next=l1;
       tail=l1;
   }
   if(l2){
       tail->next=l2;
       tail=l2;
   }

   return head;
}

解法二： 合并的新链表具有哨兵结点：

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


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
  //定义头和尾结点
  struct ListNode *head=NULL,*tail=NULL;
  //为头尾结点开辟空间
  head=tail=(struct ListNode *)malloc(sizeof( struct ListNode));
  //当两条链表中空链表
  if(l1==NULL){
      return l2;
  }
  if(l2==NULL){
      return l1;
  }
 while(l1 && l2){
      if(l1->val<l2->val){
          tail->next=l1;
          tail=l1;
          l1=l1->next;
      }
      else{
          tail->next=l2;
          tail=l2;
          l2=l2->next;
      }
  }
  //当l1还有剩余结点的时候
  if(l1){
      tail->next=l1;
  }
  //当l2还有剩余的结点的时候
  if(l2){
      tail->next=l2;
  }
  struct ListNode *list=head->next;
  free(head);

  return list;
}