前言:
🎈欢迎大家来到Dream_Chaser～的博客🎈
本文收录于 C--数据结构刷题的专栏中 -->http://t.csdn.cn/n6UEP
首先欢迎大家的来访，其次如有错误，非常欢迎大家的指正！我会及时更正错误！
一.合并两个有序链表
来源: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; }
代码执行:
本文到此结束，如有错误，随时欢迎大家指正！
