Leetcode206 reverse linked list

LeetCode206. Reverse a linked list

https://leetcode-cn.com/problems/reverse-linked-list/

Title Description

 Invert a single chain table .

 Example :

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

 Advanced :
 You can reverse the list iteratively or recursively . Can you solve the problem in two ways ？

Ideas

① Double pointer iteration

    Apply for two pointers pre( At first it pointed to NULL),cur( At first it pointed to head), then cur Keep going backwards , Save it first every time cur Next node of , After the cur Of next Pointer to pre, then pre and cur Advance one

Code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        // Application node ,pre and cur,pre Point to NULL,cur Point to head
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur){
    
            // preservation cur Next node of 
            ListNode* temp = cur->next;
            // take cur Of next Pointer to pre, Turn it over 
            cur->next = pre;
            // to update pre and cur
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

Complexity analysis :
Make n Is array length .

• Time complexity ：$O(n)$ You need to traverse the linked list once .
• Spatial complexity ：$O(1)$

---

② Recursive method

    Recursion written according to the idea of double pointer method

Code

class Solution {
    
public:
    ListNode* reverse(ListNode* pre, ListNode* cur){
    
        if(!cur)
            return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(cur, temp);
    }
    ListNode* reverseList(ListNode* head) {
    
        return reverse(NULL, head);
    }
};

There is also a recursion , It's a little difficult to understand

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        if(head==NULL || head->next == NULL)
            return head;
        // there cur Is the last node 
        ListNode* cur = reverseList(head->next);
        //head The next node of next Pointer to head
        head->next->next = head;
        // Prevent the list from cycling , send head Of next The pointer is null 
        head->next = NULL;
        // Each level of recursion returns cur, That's the last node 
        return cur;
    }
};

Refer to the big guy's problem solution