【九月打卡】第八天 反转链表
2022/9/13 4:23:18
本文主要是介绍【九月打卡】第八天 反转链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第一模块:课程介绍
课程名称:JavaScript版数据结构与算法 轻松解决前端算法面试
课程章节:LeetCode:206.反转链表
主讲老师:lewis
第二模块:课程内容
对反转链表的题目进行编写代码
第三模块:课程收获
1. 题目大概
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
解题思路
- 如何反转两个节点呢?
只需要将n+1的next指向n就好了
示例代码:
const next = p1.next; // 将下一个节点2指向它的上一个借点 p1.next = p2;
- 如何反转多个节点?
可以使用双指针遍历链表,然后重复上面的反转两个节点的操作。
双指针遍历链表指的是,假如有ab两个指针,开始的时候,b指向1,a指向null,再下一步的时候,b指向2,a指向1。直到b走到尽头就停止。
这样的话,就可以不停的反转ab就好了。
解题步骤
- 双指针一前一后遍历链表
- 反转双指针
第一步,找到位置
开始的时候,给a和b放到对应的位置去。
代码示例
var reverseList = function(head) { let b = head; let a = null; };
开始遍历链表
我们在b有值的情况下,不停的往后移,同时还要把a移动到b当前所在的位置。所以,先把b赋值给a,再把b的下一个赋值给b。
代码示例
var reverseList = function(head) { let b = head; let a = null; while(b){ console.log(b.val, a?.val) a = b; b = b.next; } };
输出:
a undefined b a c b d c
上面的双指针移动就算是完成了。那接下来就要开始做反转。也就是要把b指向a就好了。
b.next = a;
但是上面这么写的话会导致b往后移动的时候,它的下一个变成了a,结果变成了往前移动了。这样显然是不对的,所以需要找到第三者来暂时报错下这个,这样就可以继续往下走了。
示例代码:
var reverseList = function(head) { let b = head; let a = null; while(b){ const c = b.next; b.next = a; a = b; b = c; } };
那么到现在,代码算是完成了,但是需要返回a还是b呢。
因为b不停的再往后挪,到最后的时候,b就变成了undefined了,当b变成undefined的时候,a也就不挪动了。a停留在最后一个节点处。所以要返回的就是a
代码示例:
var reverseList = function(head) { let b = head; let a = null; while(b){ const c = b.next; b.next = a; a = b; b = c; } return b; };
结果
这个主要是学习双指针遍历的方法,练习双指针的使用,难点在于对反转的理解吧。开始一直搞不清楚为什么要把a = b,b=c后面才想清楚,a = b是因为要把b往后移动,b = c是要把c也往后移动,但是还要进行反转操作,所以要把b指向a,如果一开始就把b指向a的话,b的下一个节点名字就错了。所以要用c来把b的下一个节点存起来。
第四模块:课程记录
这篇关于【九月打卡】第八天 反转链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?