🔥个人主页：@草莓熊Lotso
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》
⭐️人生格言：生活是默默的坚持，毅力是永久的享受。
前言：随着编程相关知识点的学习，我们LeetCode的刷题也不能落下。在前面我们也接触到了洛谷和牛客这两个刷题网站，但是博主一直都在推荐大家使用力扣，是因为力扣的判题严谨且大部分都是接口型题目，与面试中的笔试题也更加贴合。那么还是老样子，博主会为大家提供我自己的思路和代码，但是算法题的解法肯定不止一个，欢迎大家一起交流和讨论。
目录
1.反转链表
题目描述：
题目示例：
思路： 迭代法实现链表的反转
解题过程：
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.链表的中间结点
题目描述：
题目示例：
思路： 利用快慢指针求解
解题过程：
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.合并两个有序链表
题目描述：
题目示例：
思路： 创建新链表，遍历并比较原链表中节点的值，小的尾插到新链表中
解题过程：
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语言刷题集中的题目，肯定会更加复杂一些。而且题目形式也不一样，大家需要注意一下。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持