[leetcode ladder] linked list · 206 reverse linked list

Title Description ：

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

Topic link ：

206. Reverse a linked list - Power button （LeetCode）https://leetcode.cn/problems/reverse-linked-list/

---

Their thinking ：

Fool method 1： Create a new linked list and go through it one by one

This operation should be the easiest to think of , But it is also the most complex . We need a pointer to traverse one by one from back to front , But the single linked list cannot be traversed from back to front , So we need to make a pointer traverse from front to back to the last , Then insert the node into the new linked list ; Then traverse from front to back to the penultimate , Then insert it into the single linked list ···· The time complexity of such an operation should be ：

namely , The time complexity of this algorithm will reach , Is very unsatisfactory , So this method , We directly eliminate ！

Conventional method 2： Use three pointers to flip

Next, we think of directly operating the original linked list , Flip the arrows one by one from front to back ？ We don't need to flip the numbers , Instead, try to flip the arrows between nodes ！

At this time, we need to use three pointers to flip , The logical idea is to use pointers n1 As the header of the new linked list ; The pointer n2 Used to change its pointing node next, Make the original linked list node and n1 Connected to a ; The pointer n3 Is used to keep n2 The next node address , The main logic operations are as follows ：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    if(head==NULL)
    return NULL; // If it is an empty linked list , Direct output NULL
    while(n2) //n2 It's empty , explain n2 Finished traversing the linked list 
    {
        struct ListNode* n3=n2->next; //n3 Point to the first node of the original linked list （ May be NULL）
        n2->next=n1; // take n2 Of the node currently pointed to next Point to n1
        n1=n2; // Put the header pointer of the new linked list n1 to update 
        n2=n3; //n2 Continue to take a step backwards 
    }
    return n1;
}

 

To sum up ： This problem uses three pointers to operate in a regular way , A pointer is used as the header pointer of the new linked list , A pointer is used to traverse the current linked list , The other is used to save the next node location of the current node .

Conventional method 3： Insert the linked list elements into the header

This operation is also very smart , We use a pointer to traverse from front to back , Another pointer performs header insertion on each node , The third pointer is used to reserve the address of the next node , This naturally makes the original single linked list reverse .

 

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* newHead=NULL;
    struct ListNode* cur=head;
    while(cur) // When cur It's empty time , explain cur The linked list has been traversed 
    {
        struct ListNode* next=cur->next; //cur Every step back , All set up one next preservation cur Next position of 
        cur->next=newHead; // take cur Point to the first node of the new linked list ( May be NULL)
        newHead=cur; // Point the head pointer of the linked list to cur
        cur=next; //cur Take a step back 
    }
    return newHead;
}

To sum up ： Flexibly use some basic operations when we first learn single linked list , It is the first step for us to think about every linked list problem , Some topics about linked lists come to the essence , But it will be “ Additions and deletions ” It's just a combination of operations .