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