preface

Reverse linked list is a basic quality programmers must have, often in the process of interview, written tests. I always feel that the implementation code of reverse list is not very easy to understand, so I decided to move the classic reverse list problem of Leetcode, and use more than ten diagrams to parse it, hoping to deepen everyone’s understanding of the reverse list, thank you for reading.

Leetcode’s reverse linked list original questions & answers

Reverse a single linked list.

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

Analysis:

Suppose there is a linked list 1 → 2 → 3 → ø, and we want to change it to ø ← 1 ← 2 ← 3.

As you traverse the list, change the next pointer to the current node to point to the previous element. Because a node does not reference its previous node, its previous element must be stored first. Another pointer is needed to store the next node before the reference can be changed. Don’t forget to return the 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;
}
Copy the code

Diagram list inversion code implementation

Next, we illustrate the above code implementation by adding the line number as follows:

public ListNode reverseList(ListNode head) { //1 ListNode prev = null; // 2 ListNode curr = head; / / 3while(curr ! = null) { //4 ListNode nextTemp = curr.next; //5 curr.next = prev; // 6 prev = curr; //7 curr = nextTemp; / / 8}returnprev; / / 9}Copy the code

The first line of code diagram

public ListNode reverseList(ListNode head) {  //1
Copy the code

Let’s assume that the list has 1, 2, 3 elements, followed by a null, and since the input is ListNode head, the list to be reversed is as follows:

The second line of code diagram

ListNode prev = null; / / 2Copy the code

If null is assigned to prev, that is, prev points to NULL, the graph is as follows:

The third line of code diagram

ListNode curr = head;
Copy the code

If head is assigned to curr, that is, curr points to head, the following figure can be obtained:

Loop part code diagram

 while(curr ! = null) { //4 ListNode nextTemp = curr.next; //5 curr.next = prev; // 6 prev = curr; //7 curr = nextTemp; / / 8}Copy the code

The loop part is the core part of the inversion of the linked list. Let’s go through the loop first and analyze a wave graphically.

Since curr points to head, head is not null, so the loop is entered. Let’s start with line 5:

ListNode nextTemp = curr.next; / / 5Copy the code

Next is assigned to the nextTemp variable, that is, nextTemp points to the next node of curr (node 2), and the following figure can be obtained:

Go to line 6:

curr.next = prev; / / 6Copy the code

Assign prev to curr.next because prev initialization points to NULL, i.e. curr(node 1) points to NULL. The linked list diagram looks like this:

And then we look at line 7

prev = curr; / / 7Copy the code

Assign curr to prev, and prev points to curr as shown below:

Next, we go to line 8:

curr = nextTemp; / / 8Copy the code

Assign nextTemp to curr, that is, curr points to nextTemp.

At this point, the first loop is complete. Back to the loop condition, curr is still not null, and we continue to graph it.

5-8 lines of code are executed again, resulting in the following graph:

ListNode nextTemp = curr.next; //5 curr.next = prev; // 6 prev = curr; //7 curr = nextTemp; / / 8Copy the code

Run ListNode nextTemp = curr.next; After:

Curr. Next = prev; After:

Prev = curr; After:

Curr = nextTemp; After:

Return to the while loop and execute again:

ListNode nextTemp = curr.next; //5 curr.next = prev; // 6 prev = curr; //7 curr = nextTemp; / / 8Copy the code

The graph can be obtained in sequence:

At this point, we find that curr is null and we can break out of the loop. Prev is the reverse of the linked list, so the reverse list function is implemented at line 9:

 returnprev; / / 9Copy the code

Reference and thanks

  • LeetCode website

Personal public account

  • If you are a good boy who loves learning, you can follow my public account and study and discuss with me.
  • If you feel that this article is not correct, you can comment, you can also follow my public account, private chat me, we learn and progress together.