生命如同寓言，其价值不在与长短，而在与内容。 ——塞涅卡
目录
一.链表的中间结点
1.快慢指针
二.合并两个有序链表
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 ，返回第二个结点。
做题链接：链表的中间结点
1.快慢指针
我们知道找到链表的尾结点是很容易的，我们只需要遍历整个链表，直到有个结点的next为空，即找到了尾结点。那我们如何找到中间结点呢？这里我们们又要用到双指针了，这里使用的是快慢双指针，快指针一次走两个结点，慢指针一次走一个结点。直到快指针走到尾，即慢指针走到中间结点，我们直接返回慢指针，就是中间结点的位置。
画图理解：
奇数个结点时：
偶数个结点时： 
通过画图，我们就可以很好的理解了，废话不多说，我们直接上代码：
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}二.合并两个有序链表
1.尾插法
题目介绍：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
做题链接：合并两个有序链表
这题我们可以使用尾插法，我们创建一个哨兵头结点，再一个创建一个头指针，一个尾指针，头指针始终指向最开始的头结点，为了最后的返回。我们依次取下两个链表数值小的那个结点尾接到尾，尾接一个，尾指针往后面走一位。依次类推，把所有的结点尾接起来。
我们还是一样，画图来更好的理解一下。
直接上代码：文章来源：https://www.toymoban.com/news/detail-416039.html
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
struct ListNode*head=NULL,*tail=NULL;
head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//创建头结点
while(list1&&list2)
{
if(list1->val>list2->val)
{
tail->next=list2;
list2=list2->next;
}
else
{
tail->next=list1;
list1=list1->next;
}
tail=tail->next;
}
if(list1)//退出循环，如果list1不为空，即list2尾空。
tail->next=list1;//只需要把剩下的list1尾接到最后即可
if(list2)
tail->next=list2;
struct ListNode*first=head->next;//保存哨兵位的下一个结点
free(head);//释放头结点
head=NULL;
return first;
}感谢！！！ 文章来源地址https://www.toymoban.com/news/detail-416039.html
到了这里，关于【Leetcode刷题】链表的中间结点和合并两个有序链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
