当前位置:网站首页>看一遍就理解,图解单链表反转
看一遍就理解,图解单链表反转
2020-11-07 20:56:00 【田螺男孩】
前言
反转链表是程序员必备的基本素养,经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解,决定搬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
边栏推荐
猜你喜欢
ajax 载入html后不能执行其中的js解决方法
What should be considered in the promotion plan outside the station?
一次公交卡被“盜刷”事件帶來的思考
Application and principle of handlermethodargumentresolver
不要把异常当做业务逻辑,这性能可能你无法承受
C语言Ⅰ博客作业03
使用“1”个参数调用“DownloadString”时发生异常:“操作超时”
Deep into web workers (1)
利用线程通信、解决缓存穿透数据库雪崩
【原创】ARM平台内存和cache对xenomai实时性的影响
随机推荐
Huawei HCIA notes
当 TiDB 与 Flink 相结合:高效、易用的实时数仓
Insight -- the application of sanet in arbitrary style transfer
Win10官方1909版本无法打开windows安全中心中病毒和威胁防护的实时保护解决方案。
聊聊Go代码覆盖率技术与最佳实践
阿里terway源码分析
How to think in the way of computer
编程界大佬教你:一行Python代码能做出哪些神奇的事情?
Web API系列(三)统一异常处理
在pandas中使用pipe()提升代码可读性
The prediction accuracy of the model is as high as 94%! Using machine learning to solve the 200 billion dollar inventory problem perfectly
使用“1”个参数调用“DownloadString”时发生异常:“操作超时”
ajax 载入html后不能执行其中的js解决方法
不要把异常当做业务逻辑,这性能可能你无法承受
Didi's distributed ID generator (tinyid), easy to use
Kubernetes服务类型浅析:从概念到实践
C language I blog assignment 03
Implementation of multi GPU distributed training with horovod in Amazon sagemaker pipeline mode
【C++学习笔记】C++ 标准库 std::thread 的简单使用,一文搞定还不简单?
「混合云」会是云计算的下一个战场吗?