leetcode 206. Reverse linked list

206. Reverse a linked list
     Here's the head node of the list head , Please reverse the list , And return the inverted linked list .
     Example 1：

Input ：head = [1,2,3,4,5]
Output ：[5,4,3,2,1]

Example 2：

Input ：head = [1,2]
Output ：[2,1]

Example 3：

Input ：head = []
Output ：[]

Tips ：

The number range of nodes in the linked list is [0, 5000]
-5000 <= Node.val <= 5000

Advanced ： The linked list can be inverted by iteration or recursion . Can you solve the problem in two ways ？

Method 1 ： iteration ( Double pointer )
Ideas ：
Set the current node cur, Previous node pre, The latter node next;
Traversing the linked list , change cur And pre Connection relationship of nodes , namely cur->next=pre. because pre The initial value of is the value pointed to by the last node of the linked list after inversion next, therefore pre Initialize to nullptr. And then update cur Next node .

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    } 
};

Complexity analysis ：

• Time complexity ：O(n);
• Spatial complexity ：O(1);

Mode two ： Stack
Traversing the linked list , Store the nodes on the stack separately , Then create a new head node , Take out the nodes in the stack separately , Connect behind the new head node .

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head==nullptr) return head;
        ListNode* cur = head;
        stack<ListNode*> node;
        while(cur!=nullptr){
            node.push(cur);
            cur=cur->next;
        }
        ListNode* new_head=new ListNode(0);
        ListNode* p = new_head;
        while(node.size()){
            ListNode* cur = node.top();
            node.pop();
            p->next = cur;
            p = p->next;
        }
        p->next = nullptr;
        return new_head->next;
    } 
};

Complexity analysis ：

• Time complexity ：O(n);
• Spatial complexity ：O(n);

Mode three ： recursive

class Solution {
public:
    ListNode* help(ListNode* pre, ListNode* cur){
        if(cur==nullptr) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return help(cur, temp);

    }
    ListNode* reverseList(ListNode* head) {
        return help(nullptr, head);
    } 
};

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

Complexity analysis ：

• Time complexity ：O(n);
• Spatial complexity ：O(n);