# 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
)

{

ListNode
prev
=

null
;

ListNode
curr
=
;

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
)

{

//1

ListNode
prev
=

null
;

// 2

ListNode
curr
=
;

// 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
)

{

//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
=
;``````

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 .