网站开发报价单明细,企业网站建设与维护,双鸭山网站开发,php小型网站开发前言 #x1f4da;作者简介#xff1a;爱编程的小马#xff0c;正在学习C/C#xff0c;Linux及MySQL。 #x1f4da;本文收录与初阶数据结构系列#xff0c;本专栏主要是针对时间、空间复杂度#xff0c;顺序表和链表、栈和队列、二叉树以及各类排序算法#xff0c;持…
前言 作者简介爱编程的小马正在学习C/CLinux及MySQL。 本文收录与初阶数据结构系列本专栏主要是针对时间、空间复杂度顺序表和链表、栈和队列、二叉树以及各类排序算法持续更新 相关专栏C及Linux正在发展敬请期待 目录 前言 1. 单链表基础OJ题讲解 1.1 第一题 1.2 第二题 1.3 第三题 1.4 第四题 1.5 第五题 总结 1. 单链表基础OJ题讲解
首先经过上一篇博客的学习相信同学们已经对顺序表的基础OJ题有了一定的了解那么本文继续带着大家一起来刷力扣的单链表基础题。
1.1 第一题
第一题题目链接移除链表元素
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。
题目分析我画个图给大家看一下就是如何来分析。 就是和val相同的就移除不相同的就保留返回新的头结点。
思路大家最容易想到的
拷贝等于val我就不拷贝不等于val的就拷贝到新链表最后是不是返回新链表就可以那么这个地方我用newhead和list来管理新链表。我画个图给大家看一下 代码实现如下
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* newhead NULL;struct ListNode* list NULL;while(head){if(head-val val){head head -next;}else{if(newhead NULL){newhead head;list head;head head-next;list-next NULL;}else{list-next head;head head-next;list list-next;list-next NULL;}}}return newhead;
}
1.2 第二题
第二题题目链接翻转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。
题目分析 思路
也是可以拷贝如何拷贝呢是不是还是建立一个新的一个链表newhead然后尾插head链表中的节点是不是就可以了? 代码实现
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead NULL;struct ListNode* cur head;while(cur){if(newhead NULL){head head-next;newhead cur;newhead -next NULL;cur head;}else{head head-next;cur-next newhead;newhead cur;cur head;}}return newhead;
} 1.3 第三题
第三题题目链接链表的中间节点
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。
题目分析 这道题有个很巧的方法就是用两个指针一个是快指针一个是慢指针快指针一次走两步慢指针一次走一步那么快指针走完是不是慢指针只走了一半直接返回慢指针就可以了。 代码实现
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.4 第四题
第四题题目链接返回倒数第K个节点
实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值 就是首先得先找到这个链表的尾部然后head这个指针找到离最后一个tail指针为k的地方返回这个地方的值我建议大家用count这个变量来记录。 代码实现
int kthToLast(struct ListNode* head, int k)
{int count 0;struct ListNode* tail head;while(tail){tail tail-next;count;}while(count-k){head head-next;count--;}int m head-val;return m;}1.5 第五题
第五题题目链接合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题目分析 这道题是这样子还是建立一个新链表用newhead和cur来管理然后遍历list1和list2谁小谁就放进去如果有一个链表结束了 那就把另一个链表是不是直接拷贝过去就可以。
代码实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1 NULL)return list2;if(list2 NULL)return list1;struct ListNode* newhead NULL;struct ListNode* cur NULL;while(list1 list2){if(list1-val list2-val){if(newhead NULL){newhead list1;cur list1;list1 list1-next;cur -next NULL;}else{cur - next list1;list1 list1-next;cur cur-next;}}else{if(newhead NULL){newhead list2;cur list2;list2 list2-next;cur -next NULL;}else{cur - next list2;list2 list2-next;cur cur-next;}} }if(list1){cur-next list1;}if(list2){cur-next list2;}return newhead;
} 总结
1、大家一定要动手去练习一下这些题都是很基础的单链表的OJ题可以把之前的增删查改再复习一下
2、 大家没有必要往后刷题C语言能解决的问题是有限的等后面学了C再回来看这些题就很简单。 如果这份博客对大家有帮助希望各位给小马一个大大的点赞鼓励一下如果喜欢请收藏一下谢谢大家 制作不易如果大家有什么疑问或给小马的意见欢迎评论区留言
