See once to understand, graphic single chain table inversion

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 .