引言
链表反转是C/C++中常见的问题，也是面试笔试中经常遇到的问题之一，针对此类问题，如果在内存分配方面没有特别的要求的话，直接使用vector容器较为方便；如果对内存方面要求严格控制的话，则需要使用迭代法较为稳妥。本节将对两种情况下的代码编写进行简要的分析总结。
需求描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
如当输入链表{1,2,3}时，
经反转后，原链表变为
{3,2,1}，所以
对应的输出为{3,2,1}。
以上转换过程
如下图所示：
测试样例
示例1
输入：
{1,2,3}
复制
返回值：
{3,2,1}
复制
示例2
输入：
{}
复制
返回值：
{}
复制
说明：
空链表则输出空
代码示例
思路一：在内存要求不高的时候，可以使用vector容器，先将量表内容保存到vector容器中，然后对其进行反转，最后构造新的链表，将其按照发转后的内容保存起来即可。
具体代码内容如下：
ListNode*ReverseList(ListNode*pHead)
{
if(nullptr==pHead)
{
returnnullptr;
}
vectorListNode*vec;
while(pHead)
{
vec.push_back(pHead);
pHead=pHead-next;
}
reverse(vec.begin(),vec.end());//反转vector，也可以逆向遍历
ListNode*head=vec[0];
ListNode*cur=head;
for(inti=0;ivec.size();++i){//构造链表
cur-next=vec[i];//当前节点的下一个指针指向下一个节点
cur=cur-next;//当前节点后移
}
cur-next=nullptr;//将最后一个节点的下一个指针指向nullptr，必须有此步骤
returnhead;
}
购买专栏解锁剩余41%