反转链表题目

欢迎大家来到我的博客，给生活来点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），虽然时间复杂度相同，但是代码肯定简洁不少，提升了代码的执行效率。

结语

最后感谢大家“倾听“”我的博客，感谢大家一直以来的支持！！
请一定相信相信的力量，每一滴汗水都会汇聚成滚滚长江，加油！！陌生人！！