网站首页的导航栏,网站开发技术难点,wordpress 添加悬浮窗,论文中小企业的网站建设文章目录 反转链表题目链接#xff1a;[在线OJ](https://leetcode.cn/problems/reverse-linked-list/description/)题目详解思路1#xff1a;思路1算法复杂度 思路2代码实现思路2算法复杂度 结语 欢迎大家来到我的博客#xff0c;给生活来点impetus 让我们进入《题海探骊》… 文章目录 反转链表题目链接[在线OJ](https://leetcode.cn/problems/reverse-linked-list/description/)题目详解思路1思路1算法复杂度 思路2代码实现思路2算法复杂度 结语 欢迎大家来到我的博客给生活来点impetus 让我们进入《题海探骊》感受算法之美 反转链表
题目链接在线OJ
题目详解 思路1
这里我们来说一下思路1 在上述图例中我们可以设置一个pcur在原链表中逐步往后面遍历并且在新链表中不断的去头插。这样我们就能够实现反转链表。具体对于基本的链表的增删查改等操作前面已有提及可以移步单链表进行复习。
while(pcur)
{//新链表中不断进行头插
}思路1算法复杂度
我们来计算一下时间复杂度为多少 由于需要不断往后遍历头插不需要再来遍历所以这里的时间复杂度为On 这样看是不是感觉这个思路很好了 但是再头插时需要再来malloc开辟空间以及初始化赋值等操作就会让简单的思路更加复杂化不妨换个思路。 思路2
这一次我们直接在原链表上进行操作。 首先我们需要三个指针分别为n1n2n3。 这三个指针各司其职。 请看下图
接下来我们来讨论一下为什么这个思路可行 n1作用保留n2前方的结点这样就能够赋值后方结点指向给前方结点。克服了单链表只能单向的问题。 n2作用:主要用作判断条件来使用 n3作用存储n2下一个节点防止n2赋值给n1时n2的下一个结点无法找到。 说明为什么要先n1赋值给n2在n2赋值给n3如果交换步骤的话会造成n2前方的结点找不到了形如 代码实现
struct ListNode* reverseList(struct ListNode* head) {if(headNULL){//细节判断是否为NULLreturn head;}struct ListNode*n1,*n2,*n3;n1NULL,n2head,n3n2-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;
}细节1解引用操作需要处理“防空警报“”必须拉响 细节2因为在思路2判断条件停止的上一步如果不做处理就会对NULL解引用操作。
思路2算法复杂度
只有一次循环遍历时间复杂度是On虽然时间复杂度相同但是代码肯定简洁不少提升了代码的执行效率。
结语
最后感谢大家“倾听“”我的博客感谢大家一直以来的支持 请一定相信相信的力量每一滴汗水都会汇聚成滚滚长江加油陌生人
