题目描述

题目分析

This is a popular question,Lots of school recruits,Written exams are frequent.
After a brief reading of the question, we basically understand what it is asking us to achieve
就是Invert the linked list, 如图：

Since the title does not require time complexity and space complexity,So let's get started

解决方案

思路一：翻指针方向

Start with three pointers,让n1指向NULL,n2指向链表第一个结点,n3The second node of the linked list,如图：

Generally speaking, the procedure for repeating the process is divided into three steps：

1. 初始条件
   Our initial condition is to use three pointers,respectively point to null,The first node and the second node.
2. 迭代过程
   第一步：让n2指向n1,This step realizes the flip of the first node of the linked list
   
   第二步：Let the above three pointers move back one node respectively（将n1指向n2;再让n2指向n3;最后使n3指向它的下一个结点n3->next）.
3. 结束条件
   The first step in our iterative process is to let n2去翻转,then whenn2指向NULL的时候截止.
   过程如图：
   
   

思路一代码：

struct ListNode* reverseList(struct ListNode* head){
    
    if(head==NULL)
        return NULL;
    //初始条件
    struct ListNode*n1=NULL,*n2=head,*n3=n2->next;
    while(n2!=NULL)//结束条件
    {
    
        //迭代过程
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    return n1;
}

思路二：头插法

顾名思义,Head plug method is to follow the idea of ​​head plug.Create a new linked list first,Just put the nodes in the old linked list into the new linked list by head-plugging.
第一步: 定义一个指针指向head,在定义一个新链表newHead.
第二步：定义一个next用来记录curthe latter node,将curThe node pointed to is placednewHead前面,再将newHead指向cur,cur再向后走.
旧链表head的流程图：

新链表newHead的流程图：

思路二代码：

struct ListNode* reverseList(struct ListNode* head){
    
    struct ListNode*cur=head;
    struct ListNode*newHead=NULL;
    while(cur!=NULL)
    {
    
        struct ListNode*next=cur->next;

        //头插
        cur->next=newHead;
        newHead=cur;
        cur=next;
    }
    return newHead;
}