公主请阅
- 1. 合并两个有序链表
- 1.1 题目说明
- 示例 1
- 示例 2
- 示例 3
- 1.2 题目分析
- 1.3 代码部分
- 1.4 代码分析
- 2. 链表的中间节点
- 2.1 题目说明
- 示例 1
- 示例 2
- 2.2 题目分析
- 2.3 代码部分
- 2.4 代码分析
1. 合并两个有序链表
题目传送门
1.1 题目说明
这个问题要求将两个升序链表合并成一个新的升序链表。新的链表是通过按顺序连接两个输入链表的所有节点组成的。
- 输入：两个链表，且这两个链表都是升序的。
- 输出：一个包含所有输入链表元素的升序链表。
示例 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指针进行返回就行了
