【LeetCode刷题指南】--反转链表，链表的中间结点，合并两个有序链表
🔥个人主页：@草莓熊Lotso
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》
⭐️人生格言：生活是默默的坚持，毅力是永久的享受。
前言：随着编程相关知识点的学习，我们LeetCode的刷题也不能落下。在前面我们也接触到了洛谷和牛客这两个刷题网站，但是博主一直都在推荐大家使用力扣，是因为力扣的判题严谨且大部分都是接口型题目，与面试中的笔试题也更加贴合。那么还是老样子，博主会为大家提供我自己的思路和代码，但是算法题的解法肯定不止一个，欢迎大家一起交流和讨论。
目录
1.反转链表
2.链表的中间结点
3.合并两个有序链表
1.反转链表
题目链接：206. 反转链表 - 力扣（LeetCode）
题目描述：
题目示例：
思路： 迭代法实现链表的反转
解题过程：
1.cur指向链表头结点，newhead初始化为空(用于存储反转后的新链表)
2.每次迭代中，先将cur的下一个节点next保存下来，不然后面就找不到了，然后将cur->next指向当前新链表newhead 接着让newhead来到cur的位置，再把cur移动到保存的next结点
3.循环结束后，newhead即为反转后的链表头结点
具体解题过程图示如下：
复杂度：
- 时间复杂度: O(n)
- 空间复杂度: O(1)
代码演示：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode*cur=head;struct ListNode*newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}2.链表的中间结点
题目链接：876. 链表的中间结点 - 力扣（LeetCode）
题目描述：
题目示例：
思路： 利用快慢指针求解
解题过程：
1.定义两个指针，一个slow慢指针，一个fast快指针，慢指针每次走一步，快指针每次走两步，刚开始都在头结点。
2.分两种情况讨论，当结点个数为奇数时我们可以发现fast->next为NULL时slow指针刚好走到中间结点，当结点个数为偶数时我们可以发现fast为NULL时slow指针刚好走到中间结点。
3.我们以两种不同的情况为结束条件，进行循环，当循环结束时，slow结点的位置就是中间结点的位置，返回slow就可以了
具体解题过程图示如下：
复杂度：
- 时间复杂度: O(n)
- 空间复杂度: O(1)
代码演示：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode*slow=head;struct ListNode*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;
}3.合并两个有序链表
题目描述：21. 合并两个有序链表 - 力扣（LeetCode）
题目描述：
题目示例：
思路： 创建新链表，遍历并比较原链表中节点的值，小的尾插到新链表中
解题过程：
1.如果list1或者list2中有一个为空的话，返回非空的那个
2.定义一个哨兵位的头结点和一个尾节点，申请空间；这样可以省掉后续尾插时的空节点特殊处理 3.遍历链表，注意条件，一定是两个都不能为空，然后比较大小，小的尾插到尾节点后。尾节点向前走，如果是l1的小，l1也要向前走，l2同理；
4.如果其中一个先结束，那么直接把剩下的一个链表尾插到newtail后面就行，不用循环；
5.我们最后需要返回的不是head而是head->next,定义一个新节点newhead记录下来。然后释放掉head，并置空
6.返回newhead就可以了
具体解题过程图示如下：
复杂度：
- 时间复杂度: O(1)
- 空间复杂度: O(n)
代码演示：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL)return list2;if(list2==NULL)return list1;struct ListNode* head=NULL;struct ListNode* tail=NULL;head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));while(list1!=NULL&&list2!=NULL){if(list1->val<list2->val){tail->next=list1;list1=list1->next;}else{tail->next=list2;list2=list2->next;}tail=tail->next;}if(list1!=NULL){tail->next=list1;}if (list2!=NULL){tail->next=list2;}struct ListNode*newhead=head->next;free(head);return newhead;
}往期回顾：
【LeetCode刷题指南】--数组串联，合并两个有序数组，删除有序数组中的重复项
【LeetCode刷题指南特别篇】--移除链表元素，调试技巧，链表分割
结语：本篇文章就到此结束了，《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目，肯定会更加复杂一些。而且题目形式也不一样，大家需要注意一下。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持