[Ninja Algorithm] Understanding the linked list from life scenes: the most important basic algorithm | LeetCode Question 206 Reversing the linked list

Understanding linked list inversion from life scenarios: the most important basic algorithm

Why is this question so important

Reversing the linked list seems simple, but it is the cornerstone of the linked list operation. Just like when building a house, you must first lay a solid foundation, and you must deeply understand the principle of reversal before doing complex linked list operations. Countless high-frequency interview questions are based on this: K sets of reverse link lists, judgment palindromic link lists, linked list reordering, etc. If you truly understand the reverse link list, these questions will be solved easily.

Problem description

LeetCode Question 206 "Reverse Link List" requirements: Give you the head of the single linked list, please reverse the linked list and return the reverse linked list.

For example:

Enter: 1 → 2 → 3 → 4 → 5
 Output: 5 → 4 → 3 → 2 → 1

Recursive Solution: Start with a Brief

Although recursion is not the optimal solution, its ideas are the easiest to understand. Imagine you are playing dominoes, line up all the dominoes first, and then start from the last one and push them back one by one.

The nature of recursion

The core idea of recursive inversion is:

First assume that the sub-problem has been solved (the subsequent linked list has been reversed and completed)
Then solve the problem of how the current node is connected to the reversed part

Just like if you want to complete a big project, you don’t have to consider how your subordinates complete their tasks, you just need to consider how to integrate everyone’s work.

Code implementation and detailed explanation

public ListNode reverseList(ListNode head) {
     //Basic situation: When there is an empty linked list or only one node, return directly
     if (head == null || == null) {
         return head;
     }
    
     // Recursively invert the sub-link list to obtain a new header node
     // Assuming that the subsequent linked list has been inverted, newHead points to the header node after the inverted
     ListNode newHead = reverseList();
    
     // Key steps: Connect the current node to the end of the list after the inversion
     // Assume that it is currently node 2 and node 3
     // = head means to point 3 to 2
      = head;
      = null; // Disconnect 2's original pointing to prevent the formation of rings
    
     return newHead;
 }

Iterative solution: pursuing the best space

Although iterative method is difficult to understand, it is the solution with the best spatial complexity. Let us understand deeply through a life scene.

Understanding iteration through life scenes

Imagine you are a gymnastics coach teaching a row of students to do "back roll". Every student is originally facing forward, you have to make them turn one by one. The key is: every time you deal with a student, make sure:

This student won't fall (save next pointer)
He can hold the previous student's hand (point to prev)
Get ready to hold the next student (move the pointer)

Code implementation and diagram

public ListNode reverseList(ListNode head) {
     ListNode prev = null; // The head node of the flipped part
     ListNode curr = head; // The node currently being processed
    
     while (curr != null) {
         // Step 1: Remember the next student so that you won’t be able to find him later
         ListNode nextTemp = ;
        
         // Step 2: Let the current student turn around (change the pointer pointing)
          = prev;
        
         // Step 3: Coach and assistant move one behind
         prev = curr; // prev is a "teacher assistant" who supports the student who has completed his turn
         curr = nextTemp; // curr is the "coach" to help the next student
     }
    
     return prev; // prev points to the last processed node, that is, the new header node
 }

The process diagram of iteration method

Take 1→2→3→4→5 as an example:

Initial status:
 prev = null, curr = 1
 null ← 1 → 2 → 3 → 4 → 5

 After the first iteration:
 prev = 1, curr = 2
 null ← 1 2 → 3 → 4 → 5

 After the second iteration:
 prev = 2, curr = 3
 null ← 1 ← 2 3 → 4 → 5

 Final status:
 null ← 1 ← 2 ← 3 ← 4 ← 5

Key points of in-depth understanding

1. The essence of pointer operation

Each operation changes the "point" of a node. It's like changing the direction of a person's sight. He was originally looking ahead, but now he wants to look back.

2. Invariant of iteration method

At any moment:

prev points to the part that has completed the inversion
curr points to the node being processed
nextTemp saves the pending parts

3. Why do you need three pointers

prev: Without it, I don't know where to point
curr: Without it, I don't know who to deal with now
nextTemp: Without it, the link will be broken and the subsequent nodes will not be found.

Practical application

This basic algorithm is used in many scenarios:

When processing the linked list in reverse order
When you need to determine whether the linked list is written
When you need to reverse the linked list by group
When reordering the linked list

summary

To master the reversal of linked lists:

Understand the essence of two ideas of recursion and iteration
Understand the meaning of pointer operation
Practice repeatedly until muscle memory is formed
Learn to use life scenes to deepen your understanding

Suggestion: Write this question dictatedly every day until you close your eyes and you can write it correctly. Because it is the most basic and critical operation in linked list operations, if you master it, other linked list problems will become much easier!

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~