206. reverse linked list (insert, iteration and recursion)

Create a new chain header insertion method

This method requires creating an additional linked list , Then use the head plug , In turn head The new node is inserted into the new node , Implement inversion .

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *newHead=new ListNode(0);
        while(head!=NULL)
        {
    
            ListNode *p=head->next;
            head->next=newHead->next;
            newHead->next=head;
            head=p;
        }
        return newHead->next;
    }
};

Detailed explanation ：

Iterative double pointer

This algorithm requires setting two node pointers , One before and one after , Transfer the points of nodes in the linked list , Until all nodes of the pointer are traversed .

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *pre=NULL;
        ListNode *cur=head;
        while(cur!=NULL)
        {
    
            ListNode *p=cur->next;
            cur->next=pre;
            pre=cur;
            cur=p;
        }
        return pre;
    }
};

Iteration double pointer error version

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *pre=head;// If the last node of the linked list is flipped in this way, it will not point to NULL
        ListNode *cur=head->next;// Empathy 
        while(pre!=NULL)// The termination condition here is wrong , Should be cur!=NULL
        {
    
            ListNode *p=cur;
            cur->next=pre;
            pre=p;
            cur=p->next;
        }
        return pre;
    }
};

Detailed explanation ：

recursive

Three conditions of recursion ：
1、 It can be broken down into sub problems
2、 The sub problem is solved in the same way as the original problem
3、 There is a condition for terminating recursion , The smallest question
It can be understood as a sub problem , That is, reverse the whole composed of the head node and other nodes except the head node , Then it is equivalent to reversing a linked list containing two nodes .

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *p=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return p;
    }
};

This picture is quoted from here