当前位置:网站首页>See once to understand, graphic single chain table inversion
See once to understand, graphic single chain table inversion
2020-11-07 20:56:00 【Snail boy】
Preface
Reverse linked list is the basic quality of programmers , Often in interviews 、 In the process of written examination . I always think that the implementation code of reverse linked list is not well understood , Decided to move leetcode The classic reverse list problem came out , Use more than ten pictures to analyze it , We hope to deepen our understanding of the inversion of linked list , Thank you for reading .
leetcode The original problem of reverse chain list & answer
Title Description : Invert a single chain table .
Input :
1
->
2
->
3
->
4
->
5
->
NULL
Output :
5
->
4
->
3
->
2
->
1
->
NULL
analysis :
Suppose there are linked lists 1 → 2 → 3 → Ø, We want to change it to Ø ← 1 ← 2 ← 3.
When traversing the list , Set the... Of the current node next The pointer changes to the previous element . Because the node does not refer to its previous node , So you have to store its previous element in advance . Before changing the reference , Another pointer is needed to store the next node . Don't forget to return a new header reference at the end !
Code implementation :
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
;
}
The realization of reverse code of diagram linked list
Next , We illustrate the above code implementation , First, add line number to the above implementation code , as follows :
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
}
The first line of code illustration
public
ListNode
reverseList
(
ListNode
head
)
{
//1
Let's describe the meaning according to the topic , Suppose the list has 1、2、3 An element , And then there's a null, And because the input is ListNode head, So the list to be reversed is as follows :
The second line is a code illustration
ListNode
prev
=
null
;
// 2
take null Assign a value to prev, namely prev Point to null, The available figures are as follows :
The third line is the code illustration
ListNode
curr
=
head
;
Link list head Assign a value to curr, namely curr Point to head Linked list , The available figures are as follows :
Loop part code diagram
while
(
curr
!=
null
)
{
//4
ListNode
nextTemp
=
curr
.
next
;
//5
curr
.
next
=
prev
;
// 6
prev
=
curr
;
//7
curr
=
nextTemp
;
//8
}
The loop part is the core part of the list inversion , Let's go through the cycle first , Graphic analysis of a wave .
because curr Yes head,head Not for null, So into the cycle . First of all, let's see No 5 That's ok :
ListNode
nextTemp
=
curr
.
next
;
//5
hold curr.next Assign a value to nextTemp Variable , namely nextTemp Point to curr The next node of ( That is node 2), The available figures are as follows :
Then go to 6 That's ok :
curr
.
next
=
prev
;
// 6
hold prev Assign a value to curr.next, because prev Initializing points to null, namely curr( node 1) Yes null, This is the diagram of the list :
Then we see the implementation of the 7 That's ok
prev
=
curr
;
//7
hold curr Assign a value to prev,prev Point to curr, The diagram is as follows :
next , Let's go to 8 That's ok :
curr
=
nextTemp
;
//8
hold nextTemp Assign a value to curr, namely curr Point to nextTemp, The diagram is as follows :
thus , The first cycle is over , Go back to the cycle condition ,curr Still not null, Let's go on and finish it .
5-8 Run the line code again , You can get pictures in turn :
ListNode
nextTemp
=
curr
.
next
;
//5
curr
.
next
=
prev
;
// 6
prev
=
curr
;
//7
curr
=
nextTemp
;
//8
After execution ListNodenextTemp=curr.next; after :
After execution curr.next=prev; after :
After execution prev=curr; after :
After execution curr=nextTemp; after :
Come here , Find out curr Or not for null, Back to while loop , Execute it again :
ListNode
nextTemp
=
curr
.
next
;
//5
curr
.
next
=
prev
;
// 6
prev
=
curr
;
//7
curr
=
nextTemp
;
//8
You can get pictures in turn :
Come here , We found that curr Have been to null 了 , Can jump out of the loop . Now prev It points to the reverse of the list , So the first 9 The line is finished , The function of reverse linked list is realized :
return
prev
;
//9
Reference and thanks
- LeetCode Official website
Official account number
- If you are a good child who loves learning , You can pay attention to my official account. , Study and discuss together .
- If you think there is something wrong with this article , Can comment , You can also pay attention to my official account. , Talk to me in private , Let's learn and improve together .
版权声明
本文为[Snail boy]所创,转载请带上原文链接,感谢
边栏推荐
猜你喜欢
随机推荐
High concurrency in ngnix cluster
Exploration and practice of growingio responsive programming
ngnix集群高并发
一万四千字分布式事务原理解析,全部掌握你还怕面试被问?
laravel8更新之维护模式改进
Web安全(二)---跨域资源共享
On hiz buffer
Principles of websocket + probuf
小熊派开发板实践:智慧路灯沙箱实验之真实设备接入
Jingtao project day09
Reflection on a case of bus card being stolen and swiped
聊一聊数据库中的锁
[random talk] the goal and way of software design
来自不同行业领域的50多个对象检测数据集
虚拟DOM中给同一层级的元素设置固定且唯一的key为什么能提高性能
不要把异常当做业务逻辑,这性能可能你无法承受
What is the relationship between low code vs model driven?
Three steps, one pit, five steps and one thunder, how to lead the technical team under the rapid growth?
我是如何失去团队掌控的?
Python 图片识别 OCR