[数据结构与算法](LeetCode)合并两个有序链表——C语言

题目要求

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

示例 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 均按 非递减顺序 排列

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists
?

又是一个关于链表的题目，通过之前的几篇博客的讲解，大家对链表应该有比较熟悉的理解，因此对于本篇的讲解应该更容易理解。

题目理解以及思路分析

(一) 这个题目其实难度已经降低了，题目已经给出了 升序 的两个链表，也就是说链表的顺序已经排好了，我们只需要将其按照 升序 的顺序合并即可。

(二) 相信看到这，很多读者都有了思路，比如我们先随便将两个链表合并，然后通过一个顺序排列的代码来实现排序，这样的思路是正确的，但是本篇要讲的是另外一种方法。

(三) 我们要充分利用两个链表的 升序 的这个性质，我们先不着急把两个链表合并，我们先将两个链表的数据一个一个的进行比较，小的就放入新的链表里，然后接着下一轮的比较，以此类推。

这只是我们的设想，目前来看没有什么问题，但是在实现代码的过程中会不会出现新的问题？如果出现了问题，那我们该怎么去解决呢？

代码实现

我们先来实现主要功能的代码，入下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* ans = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* p1 = list1, * p2 = list2; 
    struct ListNode* rep = ans;
     

        if((p1 -> val) <= ( p2 -> val))
        {
            rep -> next = p1;
            rep = p1;
            p1 = p1 -> next;
            length1--;
        }
        else
        { 
          rep -> next = p2;
          rep = p2; 
          p2 = p2 -> next;
          length2--;
        }

? ? ? ?

        if((p1 -> val) <= ( p2 -> val))
        {
            rep -> next = p1;
            rep = p1;
            p1 = p1 -> next;
            length1--;
        }
        else
        { 
          rep -> next = p2;
          rep = p2; 
          p2 = p2 -> next;
          length2--;
        }

这一步便是比较的步骤，同时将较小的数字放进新的链表中。

但是，细心的读者已经发现了问题？这个判断什么时候停止呢？，链表是有限的，而且两个链表的长度未必相同，如何保证每次比较都是两个链表之间的比较呢？

没错，这就是代码实现中的问题。既然问题我们已经发现了，那就该想想如何解决问题。

不要忘了一个重要的性质——两个链表都是 升序

我们可以先求出两个链表的长度分别是多少，在链表之间进行比较时，总有一个链表里面的数字最先全部放入新的链表中，这时比较停止，剩余链表的数字仍然是 升序 排列，因此全部依次放入新的链表中即可。

怎么样？现在是不是突然觉得 升序 这个条件是很关键的性质了！这样我们的思路就是完整的了，下面我们来进行分部的代码讲解。

分部代码讲解

第一部分

int Length(struct ListNode*head)
  {
      int length = 0;
      while(head)
      {
        length++;
        head = head->next;
      }
      return length;
  }

这一步是定义一个函数，用来求每个链表的长度。在之前的博客中有讲过，这里便不在过多的讲解。

第二部分

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* ans = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* p1 = list1, * p2 = list2; //定义
    struct ListNode* rep = ans;  //定义
    int length1,length2;  //定义 list1 和 list2 的对应的长度
    length1 = Length(p1); //调用函数
    length2 = Length(p2); //调用函数

?这一步主要是定义一些变量，调用上面定义的求长度的函数，为下面做铺垫。

第三部分

    while(length1 && length2) //当 length1 和 length2 中有一个为 0 ，则循环结束
    {
        //比较此时两个链表对应的值的大小
        if((p1 -> val) <= ( p2 -> val))  
        {
          rep -> next = p1;
          rep = p1;  //较小的值放入新的链表中
          p1 = p1 -> next;  //移位到链表的下一个数字
          length1--;  //链表长度减一
        }
        else
        { 
          rep -> next = p2;
          rep = p2; //较小的值放入新的链表中
          p2 = p2->next; //移位到链表的下一个数字
          length2--;  //链表长度减一
        }
    }

?第四部分

    if(length1 == 0)
       { rep -> next = p2 ; }
    else if(length2 == 0)
        { rep -> next = p1; } 
    return ans->next;
}

第四部分的实现上面讲解过，因为两个链表都是 升序 ，因此剩余的链表数据直接依次放入新的链表中即可。

return ans->next;

这一部分要特别注意，最后返回链表一定要从 ans -> next ，而不能直接返回 ans 。?

第五部分

完整的代码：

int Length(struct ListNode*head)
  {
      int length = 0;
      while(head)
      {
        length++;
        head = head->next;
      }
      return length;
  }
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* ans = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* p1 = list1, * p2 = list2; //定义
    struct ListNode* rep = ans;  //定义
    int length1,length2;  //定义 list1 和 list2 的对应的长度
    length1 = Length(p1); //调用函数
    length2 = Length(p2); //调用函数
    while(length1 && length2) //当 length1 和 length2 中有一个为 0 ，则循环结束
    {
        //比较此时两个链表对应的值的大小
        if((p1 -> val) <= ( p2 -> val))  
        {
          rep -> next = p1;
          rep = p1;  //较小的值放入新的链表中
          p1 = p1 -> next;  //移位到链表的下一个数字
          length1--;  //链表长度减一
        }
        else
        { 
          rep -> next = p2;
          rep = p2; //较小的值放入新的链表中
          p2 = p2->next; //移位到链表的下一个数字
          length2--;  //链表长度减一
        }
    }
    if(length1 == 0)
       { rep -> next = p2 ; }
    else if(length2 == 0)
        { rep -> next = p1; } 
    return ans->next;
}