建设网站和备案,旅游网站建设目标意义,网站设计免费模板,wordpress地址和站点地址区别欢迎来到我的#xff1a;世界
收录专栏#xff1a;链表
希望作者的文章对你有所帮助#xff0c;有不足的地方还请指正#xff0c;大家一起学习交流 ! 目录 前言第一题#xff1a;删除链表的倒数第n个节点第二题#xff1a;链表的中间结点第三题#xff1a;合并两个排序…
欢迎来到我的世界
收录专栏链表
希望作者的文章对你有所帮助有不足的地方还请指正大家一起学习交流 ! 目录 前言第一题删除链表的倒数第n个节点第二题链表的中间结点第三题合并两个排序的链表 总结 前言
在这里写的是有关链表的落坑题详细写了我落坑的全过程相信大家也都掉过坑该专栏我会持续更新感谢铁子们的支持。 -———————对过程全力以赴对结果淡然处之 第一题删除链表的倒数第n个节点 地址 oj题地址 解题思路 1.暴力遍历 我们先遍历一遍找到该链表中有多少个节点(第一次遍历)然后再第二次遍历找到倒数第n个节点再进行删除再返回原地址。这种方法可以说是这道题的比较简单的实现方法。再这里我想讲一下另一种方法 2.三指针法 先创造三个指针tail指针sur指针dst指针而surdst指针一开始指向是链表的起始地址tail指针是指向sur指针前一个字节的地址这就需要重新开辟一块空间其中的next 可以找到sur的地址 起始时物理图 注意链表因为地址不是相连的其地址可以看作是随机的图中的地址都是我随便编的,只是为了方便更容易观察 思路先让dst指针向后走n个节点这样的话dst指针和sur指针就相距了n个节点然后让这三个指针一起向后一次移动一个节点直到dst指针指向空指针这样的话sur所指的就是倒数第n个节点(这一步观念很重要一定要想清楚),这个时候有要删除的那个节点地址也有该节点上一个节点的地址tail指针所指那就可以很好的完成删除。 以上的是思路下面来进行实现 结束时的物理图 struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {// write code here//sur指针是指向要删除的那个节点dst是与sur保持间距n的tail是sur前一个节点struct ListNode* sur head, *dst head;struct ListNode*tail (struct ListNode*)malloc(sizeof(struct ListNode));tail-nextsur;//先让dst指针走n个节点while (n--) {dst dst-next;}while (dst) {//三个指针一起出发tail指针始终指向sur指针前前一个节点 dst dst-next;sur sur-next;tail tail-next;}//删除if (head sur) {//如果sur没动说明要删的就在第一个head head-next;sur head-next;} else {//要删的只要找到sur指针的前一个节点就可以让sur后一个节点与之相连tail-next sur-next;}return head;
}第二题链表的中间结点 地址oj地址 解题思路 1.暴力遍历法 根据这道题的正常思路肯定是先遍历一遍该链表的所有结点的个数就可以得出中间点了最后返回指向该点的地址这种方法很寻常在这里我就不具体讲了我想具体讲下一种方法2.快慢指针法 该方法思路是先设置两个指针slowfast分别是快慢指针首先两个指针都是指向链表的起始位置slow向下一个结点移动而fast向下两个结点移动直到fast指针停下那fast指针什么时候停呢肯定有不同情况如果链表的结点时偶数时这时fast 走到空为止而如果链表总结点时奇数时,这时fast走到尾结点停下。 ----如为奇数时逻辑图 第一步 第二步 第三步 若为偶数时 逻辑图: 第一步 第二步 第三步 第四步 代码
struct ListNode* middleNode(struct ListNode* head ) {// write code here//设置快慢指针struct ListNode*surhead,*dsthead;//当dst指针为空或dst指向的next为空就停下while(dst dst-next){sursur-next;dstdst-next-next;}return sur;
}第三题合并两个排序的链表 地址oj地址 解题思路 首先链表和顺序表不同有些思路是行不通的但也有其优点链表是由一个一个结点连起来的可以随时拆下来的 用归并的方法我们可以先创造两个指针让需要归并的两组链表由起始位置进行比较较小值尾插入一个指针另一个指针是找到需要插入的前一个结点好方便尾插 比较12尾插入 1 如果是第一次插入应该先让head指针和tail指针同时指向 1 的地址如果不是第一次插入那就是应该pHead1的地址给tail-next然后让tail指针指向tail-next最后让pHead1指向下一个结点 然后是 23 尾插入2的地址跟上面的步骤一样 注意这里之后就不是第一次插入记得让tail指针指向tail的下一个结点 后面的步骤几乎是一样的 直到有一个链表没有了在将剩下链表直接进行尾插入就可以了 最后返回head指针 但是这就对了么 不是的还有一步我们忘记了如果两个链表其中一个是空那这个程序的结果肯定报错所以我们还要在最开始进行判断如果有其中一个为空则直接返回另一个链表 代码
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {// write code here//如果其中一个链表为空则直接返回另一个链表if(pHead1NULL)return pHead2;if(pHead2NULL)return pHead1;struct ListNode* head NULL, *tail NULL;//判断哪个链表先为空就跳出去while (pHead1 pHead2) {if (pHead1-val pHead2-val) {if (tail NULL) {//第一次尾插head tail pHead1;} else {//不是第一次尾插tail-next pHead1;tailtail-next;}//让篇pHead1指针找到下一个结点pHead1 pHead1-next;} else {if (tail NULL) {//第一次尾插head tail pHead2;} else {//不是第一次尾插tail-next pHead2;tailtail-next;}//让篇pHead2指针找到下一个结点pHead2 pHead2-next;}}//判断哪个链表先为空然后让另一个链表直接尾插入
if(pHead1)tail-nextpHead1;if(pHead2)tail-nextpHead2;return head;
}总结
在这里感谢老铁们的观看在这里小孩谢谢大家的支持以上的题目都是基于小孩现在的能力来说如果还有更好的方法的老铁可以在评论区里面一起进行讨论哦在后面随着小孩的知识储备越多小孩肯定还会加以优化优化 到了最后 我还想告诉你 ------------对过程全力以赴对结果淡然处之 也是对我自己讲的
