[sword finger offer] interview question 24 Reverse linked list

Interview questions 24. Reverse a linked list

subject

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 .

Ideas

  Define three pointers ,pre,cur,temp; When I need to adjust nodes cur Of next When the pointer , Besides knowing the nodes i In itself , You also need to know its previous node h, The nodes i Of next The pointer points to the node h, We also need to save the nodes i The next node of J, To prevent the linked list from being disconnected . When we put nodes i Of next Point to previous node h When , At this time will be Pre Pointer to i,cur The pointer points to the node temp;

Code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        ListNode *current = head,*pre = nullptr;
        while(current != nullptr)
        {
    
            ListNode *tmp = current->next;// Store the next node 
            current->next = pre;//  Set the... Of the current node next Point to previous node 

            //  After the modification   The current node becomes pre
            pre = current;          // pre Staging the current node 
            current = tmp;         //  Current pointer to temporary node 
        }
        return pre;
    }
};