题目描述：
给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
数据范围： n小于等于1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例：
输入：
{1,2,3}
返回值：
{3,2,1}
解题思路：
本题考察数据结构链表的使用。有两种解法：
- 结合vector解，将链表指针存放在vector中，进行反转操作，再依次赋给新的链表nhead即可。
- 用链表指针解，使用三个指针pre、cur、nex，nex即原链表指向下一个，cur即原链表当前指向，pre为原链表前一个指针。令nex=cur->next，将下一个指针临时存放在nex；cur->next=pre，表示将当前指针指向前一个指针，也就是反向指向；pre=cur，cur=nex，即指针后移，然后就可以操作下一个指针了。当cur为空时遍历完成，此时的pre就是反转好的链表。
测试代码：
解法一，结合vector：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(!pHead) return nullptr; vector<ListNode*> v; while(pHead) { v.push_back(pHead); pHead=pHead->next; } reverse(v.begin(),v.end()); ListNode *nhead=v[0]; ListNode *nex=nhead; for(int i=1;i<v.size();++i) { nex->next=v[i]; nex=nex->next; } nex->next=nullptr; return nhead; } };
解法二，链表指针：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode *pre=nullptr; ListNode *cur=pHead; ListNode *nex=nullptr; while(cur) { nex=cur->next; cur->next=pre; pre=cur; cur=nex; } return pre; } };
