当前位置:网站首页>看一遍就理解,图解单链表反转
看一遍就理解,图解单链表反转
2020-11-07 20:56:30 【田螺男孩】
前言
反转链表是程序员必备的基本素养,经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解,决定搬leetcode那道经典反转链表题出来,用十多张图去解析它,希望加深大家对链表反转的理解,谢谢阅读。
leetcode的反转链表原题&答案
题目描述: 反转一个单链表。
输入:
1
->
2
->
3
->
4
->
5
->
NULL
输出:
5
->
4
->
3
->
2
->
1
->
NULL
分析:
假设存在链表 1 → 2 → 3 → Ø,我们想要把它改成 Ø ← 1 ← 2 ← 3。
在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用!
代码实现:
public
ListNode
reverseList
(
ListNode
head
)
{
ListNode
prev
=
null
;
ListNode
curr
=
head
;
while
(
curr
!=
null
)
{
ListNode
nextTemp
=
curr
.
next
;
curr
.
next
=
prev
;
prev
=
curr
;
curr
=
nextTemp
;
}
return
prev
;
}
图解链表反转代码的实现
接下来,我们图解以上代码实现,先对以上实现代码加上行号,如下:
public
ListNode
reverseList
(
ListNode
head
)
{
//1
ListNode
prev
=
null
;
// 2
ListNode
curr
=
head
;
// 3
while
(
curr
!=
null
)
{
//4
ListNode
nextTemp
=
curr
.
next
;
//5
curr
.
next
=
prev
;
// 6
prev
=
curr
;
//7
curr
=
nextTemp
;
//8
}
return
prev
;
//9
}
第一行代码图解
public
ListNode
reverseList
(
ListNode
head
)
{
//1
我们顺着题目描述意思,假设链表就有1、2、3个元素吧,后面还跟着一个null,又因为输入是ListNode head,所以这个即将要反转的链表如下:
第二行代码图解
ListNode
prev
=
null
;
// 2
将null赋值给prev,即prev指向null,可得图如下:
第三行代码图解
ListNode
curr
=
head
;
将链表head赋值给curr,即curr指向head链表,可得图如下:
循环部分代码图解
while
(
curr
!=
null
)
{
//4
ListNode
nextTemp
=
curr
.
next
;
//5
curr
.
next
=
prev
;
// 6
prev
=
curr
;
//7
curr
=
nextTemp
;
//8
}
循环部分是链表反转的核心部分,我们先走一遍循环,图解分析一波。
因为curr指向了head,head不为null,所以进入循环。先来看第5行:
ListNode
nextTemp
=
curr
.
next
;
//5
把curr.next 赋值给nextTemp变量,即nextTemp 指向curr的下一节点(即节点2),可得图如下:
再执行到第6行:
curr
.
next
=
prev
;
// 6
把prev赋值给curr.next,因为prev初始化化指向null,即curr(节点1)指向了null,链表图解成这样了:
然后我们看执行到第7行
prev
=
curr
;
//7
把curr赋值给prev,prev指向curr,图解如下:
接着,我们执行到第8行:
curr
=
nextTemp
;
//8
把nextTemp赋值给curr,即curr指向nextTemp,图解如下:
至此,第一遍循环执行结束啦,回到循环条件,curr依旧不为null,我们继续图解完它。
5-8行代码又执行一遍,依次可得图:
ListNode
nextTemp
=
curr
.
next
;
//5
curr
.
next
=
prev
;
// 6
prev
=
curr
;
//7
curr
=
nextTemp
;
//8
执行完 ListNodenextTemp=curr.next;后:
执行完 curr.next=prev;后:
执行完 prev=curr;后:
执行完 curr=nextTemp;后:
来到这里,发现curr还是不为null,再回到while循环,再执行一遍:
ListNode
nextTemp
=
curr
.
next
;
//5
curr
.
next
=
prev
;
// 6
prev
=
curr
;
//7
curr
=
nextTemp
;
//8
依次可得图:
来到这里,我们发现curr已经为null了,可以跳出循环了。这时候prev指向的就是链表的反转呀,所以第9行执行完,反转链表功能实现:
return
prev
;
//9
参考与感谢
- LeetCode 官网
个人公众号
- 如果你是个爱学习的好孩子,可以关注我公众号,一起学习讨论。
- 如果你觉得本文有哪些不正确的地方,可以评论,也可以关注我公众号,私聊我,大家一起学习进步哈。
版权声明
本文为[田螺男孩]所创,转载请带上原文链接,感谢
https://blog.51cto.com/14989534/2547468
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World