Leetcode daily practice 206. Reverse the linked list

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 206. Reverse a linked list

Let’s get it！

---

---

1. Topic analysis

Here's the head node of the list head , Please reverse the list , And return the inverted linked list .

Example 1：

Example 2：

Example 3：

2. Title diagram

There are two solutions to this problem

Train of thought ： Three pointer reversal

Definition 3 A pointer to the n1、n2、n3：

The pointer n1 Point to NULL;
 
The pointer n2 Point to the head node ;
 
The pointer n3 Point to the second node , That is to say n2->next;

n1 and n2 In order to pour Pointer pointing ,n3 To save the next （ As shown in the figure ）.

The first 1 Step , hold n2 Of next Point to n1（ As shown in the figure ）

And then put n2 Address assigned to n1, hold n3 Address assigned to n2,n3 be equal to n3 Of next （ As shown in the figure ）

Then follow the above steps to iterate and cycle back , When n2 Point to NULL（ empty ） when , Just close the loop , At this time, the linked list is reversed successfully （ As shown in the figure ）

here , The new head node is n1, Just go back .

it is to be noted that ：
（1） If it is an empty linked list , Then go straight back NULL.
（2） If n3 Of next Not empty , that To perform n3 = n3->next

Interface code

struct ListNode* reverseList(struct ListNode* head){
    
    if (head == NULL) {
    
        return NULL;
    }
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
    while (n2) {
    
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3) {
    
            n3 = n3->next;
        }
    }
    return n1;
}

Submit results

Train of thought two ： The first interpolation

Define pointer cur Point to the head node of the list ;
 
Create a new linked list , And define the head of the new linked list as newHead , Point to NULL;
 
then cur Take the original linked list node , Then insert your head into newHead The new linked list .
 
The idea is ： Traverse Old linked list , Get the node New linked list , Perform head insertion

Before head insertion , Define a curNext Used to hold cur Point to the next.（ As shown in the figure ）

The first 1 Step , hold cur Of next Point to newHead, As shown in the figure

And then update newHead（newHead = cur） , And let cur（cur = curNext） Go back to the original curNext The location of , And then let curNext Go to its next Location （ As shown in the figure ）

The first 2 Step , hold cur Of next Point to newHead, As shown in the figure

And then update newHead（newHead = cur） , And let cur（cur = curNext） Go back to the original curNext The location of , And then let curNext Go to its next Location （ As shown in the figure ）

The first 3 Step , hold cur Of next Point to newHead, As shown in the figure

And then update newHead（newHead = cur） , And let cur（cur = curNext） Go back to the original curNext The location of , And then let curNext Go to its next Location （ As shown in the figure ）

The first 4 Step , hold cur Of next Point to newHead, As shown in the figure

And then update newHead（newHead = cur） , And let cur（cur = curNext） Go back to the original curNext The location of , And then let curNext Go to its next Location （ As shown in the figure ）

At this time, there is only one left ,cur It's not empty , Then continue cur Of next Point to newHead, As shown in the figure

here curNext It's already empty , its next Location does not exist , So no more execution curNext = curNext->next;

And then update newHead（newHead = cur） , And let cur（cur = curNext） Go back to the original curNext The location of （ As shown in the figure ）

Be careful ： When cur It's empty time , The loop ends , Then the linked list is reversed ！

Interface code

struct ListNode* reverseList(struct ListNode* head) {
    
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;
    while (cur) {
    
    	//  Save before inserting cur The next node of 
        struct ListNode* curNext = cur->next;
        //  Head insertion 
        cur->next = newHead;
        newHead = cur;
        cur = curNext;
        if (curNext) {
    
            curNext = curNext->next;
        }
    }
    return newHead;
}

Submit results