1. 合并两个有序链表

题目传送门

---

1.1 题目说明

这个问题要求将两个升序链表合并成一个新的升序链表。新的链表是通过按顺序连接两个输入链表的所有节点组成的。

1. 输入：两个链表，且这两个链表都是升序的。
2. 输出：一个包含所有输入链表元素的升序链表。

示例 1

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

示例 2

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

示例 3

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

这个问题的主要任务是遍历两个链表，按大小顺序逐个节点合并，形成一个新的升序链表。

---

1.2 题目分析

将两个链表合成为一个链表并且将表头返回，那么我们应该怎么做呢？
对于这个题我们可以先将特殊情况进行处理，如果其中一个链表是空的，那么我们将剩下的那个进行返回操作就行了

解决完特殊情况后我们就进行这道的思路讲解了

我们可以对两个链表进行遍历的操作，然后比较对应的节点的大小，在此之前我们先创建一个哨兵位用来占位子，如果哪个节点大的话我们就让哨兵位的nxet指向指向谁
然后我们就一次进行遍历，这个相当于在两个链表的基础上创建了一个新链表，在判断完大小之后，我们遍历两个链表的指针往后走，我们的哨兵位的指针也往后走
等循环结束之后，我们肯定是有一个链表处理完了，但是还有一个链表还有剩余的节点的
如果哪个链表还是剩余的节点，我们直接让在哨兵位开始遍历的指针进行next指针的指向操作就行了，将剩余的节点接在后面就行了
最后，因为我们的哨兵位是一个空壳，我们返回的是哨兵位的下个节点，这个节点才是名副其实的头结点

---

1.3 代码部分

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*//*先把特殊情况归类出来，然后我们再进行题目分析两个链表合并，我们是需要一个新的链表进行数据的存储的逐个对l1和l2的节点内的数据大小进行比较，通过while循环，那么结束条件是什么呢？*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//特殊情况下if(list1==NULL){return list2;}else if(list2==NULL){return list1;}ListNode *ps=(ListNode*)malloc(sizeof(ListNode));//创建一个伪头节点ListNode*tmp=ps;while(list1!=NULL&&list2!=NULL){if(list1->val<=list2->val)//l1节点的值小于等于l2节点的值{tmp->next=list1;//那么list1就是这个伪节点的下一个节点list1=list1->next;//换下一个节点}else{tmp->next=list2;list2=list2->next;}tmp=tmp->next;//伪节点往后走}//到这里要么两个链表都处理完了，要么就是还剩下一个链表if(list1!=NULL){tmp->next=list1;}if(list2!=NULL){tmp->next=list2;}return ps->next;//因为ps是个伪节点，不存储真实的数据
}

---

1.4 代码分析

我们先将特殊情况进行处理了
处理完成之后我们先动态申请一个伪头结点ps
然后我们创建一个指针tmp指向这个头结点
然后我们可以开始进行循环遍历两个链表同时进行判断操作了
我们使用while循环，循环结束的条件就是两个链表的指针都不能是空，就是说我们的链表到尾节点就停下来
在循环中我们进行两个指针对应节点的判断，如果哪个节点对应的值小的话，我们就让我们的tmp指针的next指向这个节点
然后我们被指向的节点指向完成之后，上面的指针就往后进行遍历继续比较大小
然后在一轮比较结束之后，我们的tmp也需要往后面走一步进行遍历操作
然后出了循环，我们的两个链表要么都处理完了，要么就是存在一个链表有剩余的节点
我们直接让tmp指向剩余链表的节点了
最后我们返回这个哨兵位的的下个节点，这个节点就是有效的节点了

---

2. 链表的中间节点

题目传送门

---

2.1 题目说明

给你单链表的头结点 head，请你找出并返回链表的中间结点。

• 如果有两个中间结点，则返回第二个中间结点。

示例 1

• 输入：head = [1,2,3,4,5]
• 输出：[3,4,5]
• 解释：链表只有一个中间结点，值为 3。

示例 2

• 输入：head = [1,2,3,4,5,6]
• 输出：[4,5,6]
• 解释：该链表有两个中间结点，值分别为 3 和 4，返回第二个结点。

---

2.2 题目分析

我们需要求出这个链表的中间节点，那么我们应该怎么实现呢？
我们是可以利用快慢指针进行这个效果的实现的
我们让慢指针走一步，快指针走两步
然后我们快指针到尾节点的时候，我们慢指针刚好在中间的位置
那么这个时候我们直接将慢指针进行返回的操作就行了

---

2.3 代码部分

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{//利用快慢指针ListNode*slow=head;ListNode*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;}

---

2.4 代码分析

我们创建了两个指针

• slow慢指针—走一步每次
• fast快指针----走两步每次

利用好数学规律，我们就将这个题解决了
我们利用while循环进行链表的遍历操作
循环条件就是fast!=NULL&&fast->next!=NULL

那么这个条件能不能换过来呢？
在你的快慢指针算法中，循环条件 while (fast != NULL && fast->next != NULL) 是确保快指针能安全地前进。我们来讨论如果将条件顺序换成 while (fast->next != NULL && fast != NULL) 会发生什么。

原始条件分析：

while (fast != NULL && fast->next != NULL)

这里的顺序先检查 fast != NULL，再检查 fast->next != NULL。这样做的原因是：

• 先检查 fast != NULL 可以确保在访问 fast->next 之前，fast 指针是有效的（即不为 NULL）。
• 如果先检查 fast->next != NULL 而 fast 本身已经是 NULL，就会导致程序崩溃，因为 NULL->next 是非法操作。
  如果换成 fast->next != NULL && fast != NULL：

while (fast->next != NULL && fast != NULL)

在这种情况下，编译器首先会检查 fast->next != NULL，但是如果 fast 本身是 NULL，就会试图访问 NULL->next，导致未定义行为或者程序崩溃。

为什么不能换过来？
如果 fast 是 NULL，则它没有任何成员可以访问，包括 next。因此，必须首先检查 fast 是否是 NULL。否则，会出现对空指针的非法访问，导致运行时错误。

结论
条件 不能换过来。必须先检查 fast != NULL，确保 fast 不是空指针，然后再检查 fast->next。

然后我们快指针走一步，慢指针走两步，等到循环结束之后，慢指针就在中间节点上，我们将slow指针进行返回就行了