【DAY 1.数据结构之反转链表1.牛客网BM1】

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、对于一整串完整链表的反转
• 二、使用步骤
• • 1.引入库
• 总结

前言

对数据结构的重新学习，这是在牛客网上找的简单题中的对数据结构中链表的反转。

一、对于一整串完整链表的反转

示例：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：
0≤𝑛≤1000 0≤n≤1000
要求：空间复杂度 𝑂(1) ，时间复杂度 𝑂(𝑛)

二、使用步骤

1.引入库

代码如下（示例）：
方法一：运用三个指针

structListNode*ReverseList(structListNode*head){structListNode*first=NULL;structListNode*second=head;structListNode*third;while(second!=NULL){third=second->next;second->next=first;first=second;second=third;}returnfirst;

方法二：递归法。
一直递，直到head=2,head->next=3,newhead=3,
现在解释对head->next->next=head的理解：
head->next=3,然后3的下一个指向2，即3->2，
为了防止成为一个环，将2的下一个指向NULL。

structListNode*ReverseList(structListNode*head){if(head==NULL||head->next==NULL){returnhead;}structListNode*newhead=ReverseList(head->next);head->next->next=head;head->next=NULL;returnnewhead;}

方法三：新建虚拟头节点，遍历原链表，把每一个节点都头插到虚拟节点后。

structListNode*ReverseList(structListNode*head){structListNode*newhead=NULL;structListNode*p;while(head!=0){p=head;//将头节点存到p里面head=head->next;//向后移动p->next=newhead;//将当前遍历节点放到新头节点后面newhead=p;//当前节点作为新头节点}returnnewhead;}

总结

提示：这里对文章进行总结：
本文介绍了三种反转链表的方法，