链上的羁绊，数据与节点的暗涌心跳

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指针进行返回就行了