Sword finger offer:[day 2 linked list (simple)] --- > reverse linked list

---

One 、 Title Description

Define a function , Enter the head node of a linked list , Invert the linked list and output the head node of the inverted linked list .

Example
Input : 1->2->3->4->5->NULL
Output : 5->4->3->2->1->NULL

Limit
0 <= Number of nodes <= 5000

Two 、 Thought analysis

Ideas

① Suppose the linked list is $1\to 2\to 3\to \varnothing$, We want to change it to $\varnothing \leftarrow 1\leftarrow 2\leftarrow 3$.
② When traversing a linked list , Change the current node's next The pointer is changed to point to the previous node . Because it's a one-way list , Therefore, the previous node must be stored in advance . meanwhile , Of the current node next After the pointer is changed to point to the previous node , Continue to process the next node . The current node's next The pointer no longer points to the following node , We can't find the next node , Therefore, you are changing the current node next Before the pointer , You also need to store the following node . Last , After the current node is reversed , Move to the next node , The node in front of the current node also moves back .
③ Loop through the above steps , Until the current node is empty . At this point, it means that we have reached the end of the chain next node , Just return the previous node of the current node .

3、 ... and 、 The overall code

The overall code is as follows

struct ListNode* reverseList(struct ListNode* head){
    
    // establish pre The pointer , Point to the node before the current node . This is because if you want to reverse the current node , Of the current node next Point to pre
    struct ListNode* pre = NULL; 
    // The current node is not empty , Description can also be reversed 
    while(head){
    
        // Save the next node of the current node , Because the current node is reversed , Of the current node next Point to pre 了 , You don't know the next node that needs to be reversed 
        struct ListNode* next = head->next;
        head->next = pre; // Reverse 
        pre = head;  //pre move backward 
        head = next; // Move the current node backward 
    }
    // because head Finally, it will be the node behind the last node , It's an empty , So back pre
    return pre;
}

function , The test passed