【链表OJ 5】合并两个有序链表

前言:

🎈欢迎大家来到Dream_Chaser～的博客🎈

本文收录于 C--数据结构刷题的专栏中 -->http://t.csdn.cn/n6UEP

首先欢迎大家的来访，其次如有错误，非常欢迎大家的指正！我会及时更正错误！

一.合并两个有序链表

1.1核心逻辑

1.2两元素相同时选谁尾插?

一.合并两个有序链表

来源:21. 合并两个有序链表 - 力扣（LeetCode）

题目:

解析:

        函数的参数是两个指向 ListNode 结构体的指针, ListNode 是一个常见的链表节点结构。ListNode 结构一般包含两个成员：一个是存储节点值的变量（比如 val ），另一个是指向下一个节点的指针（比如 next ）。



        目的是把两个已排序的链表（ list1 和 list2 ）合并为一个新的已排序的链表，并返回这个新链表的头节点。

1.1核心逻辑

以下是该函数的核心逻辑：

首先，如果 list1 或 list2 是空链表（即NULL），函数会直接返回另一个链表。这是因为合并一个空链表和一个非空链表的结果就是那个非空链表。
接着，它进入了一个while循环。在这个循环中，只要list1 和list2都不为空，就会比较它们当前节点的值。如果 list1 的当前节点值小于 list2 的当前节点值，就把list1 的当前节点加入到新链表中(先让tail -> next= list1 ,然后tail=tail->next 指向list1)，,然后 list1 把向后移动一位,。否则，就把list2的当前节点加入到新链表中(先让tail -> next= list2 ,然后tail=tail->next 指向list2)，然后把list2向后移动一位。这样可以保证新链表的节点是按照升序排列的。
head和 tail 是两个辅助指针，用来构建新链表。head指向新链表的头节点，tail指向新链表的尾节点。每次添加一个新节点时，都会更新tail指向新加入的节点。
当list1或 list2 中有一个被完全遍历（即变为NULL）后，while循环就会结束。此时，如果list1或list2中还有剩余的节点，就把这些节点全部加入到新链表的尾部。这是可以做的，因为这些剩余的节点已经是按照升序排列的，而且它们的所有值都大于新链表中已有节点的值。
最后，函数返回新链表的头节点 head

1.2两元素相同时选谁尾插?

我解释一下为什么当list1指向的元素与list2指向的元素大小相等时，用list2尾插：

在两个链表元素相等的情况下，默认选择lsit1作为较大的元素。

当list1和list2指向的元素都是1时，来到了if else 语句，如果条件为真，进入循环，则证明选择list2作为较大元素,反之选择list1为较大元素

结果程序来到了else处，此刻list2小于list1，选择list2尾插,说明list1比list2大

动图解析:(点进去放大看更清晰)

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
   if(list1==NULL)
      return list2;//若第一个链表为 NULL，直接返回第二个链表
   if(list2 ==NULL)
      return list1;//若第二个链表为 NULL，直接返回第一个链表

   struct ListNode* head=NULL,*tail=NULL;
   while(list1 && list2)
   {
     if(list1->val < list2->val)//比较链表元素谁大,核心是小的先为尾插
     {
         if(tail==NULL)
          {
             head= tail= list1;
          }
         else
          {
            tail->next=list1;//让新链表的结点与list1指向的元素想链接
            tail=tail->next;
          }
        list1=list1->next;//list1往原始链表后面遍历
     }
   else
   {
      if(tail == NULL)
       {
           head= tail =list2;
       }
      else
       {
          tail->next=list2;//让新链表的结点与list2指向的元素想链接
          tail=tail->next;
      }
         list2=list2->next;//list2往原始链表后面遍历
      }
   }
//若其中一个链表已经遍历到NULL，直接把另一个链表的所有元素原封不动拷贝到新链表
     if(list1)
     {
        tail->next=list1;
     }
     
     if(list2)
     {
      tail->next=list2;
     }
    return head;
 }

代码执行: