Leetcode question brushing record ｜ 206_ Reverse linked list

author github link ： github link

Force to buckle 206 topic

type ： Linked list

subject ：

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 ：[]

Their thinking

Train of thought reminder ： Three nodes are used to traverse
Train of thought details ：

1. Define two pointers ：prev: Front pointer node ;curr: Current pointer node
2. The front pointer node points to null,curr On the linked list head It's about
3. curr!=null It's been circulating
4. Because the next step prev Yes curr->next, The linked list behind the connection is about to be disconnected , This is our preparation in advance , To get a next The pointer is used as a temporary mark for the following linked list , In order to curr Iterate back .
5. curr->next The value after the original link , Now let it disconnect , To make the prev To connect curr->next.
6. prev Move back ,curr Move back （ Here we use the previously prepared temporary variables next, It's because of next, To make curr Find the next position to continue the iteration ）
7. Iteration complete , Returns the entire list , Implement inversion

c++

/** * 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) {
    
        /*  Define two pointers ： prev: Front pointer node  curr: Current pointer node  */ 
        ListNode * prev = NULL;// The front pointer node points to null
        ListNode *curr = head;//curr On the linked list head It's about 
        while(curr){
    //curr!=null It's been circulating 
            ListNode *next = curr->next;// Because the next step prev Yes curr->next, The linked list behind the connection is about to be disconnected , This is our preparation in advance , To get a next The pointer is used as a temporary mark for the following linked list , In order to curr Iterate back .
            curr->next = prev;//curr->next The value after the original link , Now let it disconnect , To make the prev To connect curr->next
            prev = curr;//prev Move back 
            curr = next;//curr Move back （ Here we use the previously prepared temporary variables next, It's because of next, To make curr Find the next position to continue the iteration ）
        }
        return prev;// Iteration complete , Returns the entire list , Implement inversion 

    }
};

python

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr is not None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

Problem solving sketch paper （ For reference only , If there is any mistake, please correct it ）