反转链表题目

文章目录

反转链表
- 题目链接：[在线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;
}