题目描述：
输入一个链表，反转链表后，输出新链表的表头。
测试用例：
1）功能测试（输入的链表含有多个节点、链表中只有一个节点）
2）特殊输入测试（链表头节点为nullptr指针）
解题思路：
1）最普通的方法：定义三个指针，从头节点开始遍历，一点一点反转链表至链表结束。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == nullptr)
return nullptr;
if(pHead->next == nullptr)
return pHead;
ListNode* preNode = pHead;
ListNode* currNode = pHead->next;
ListNode* tempNode = nullptr;
while(currNode!=nullptr){
tempNode = currNode->next; //可能会为空
if(preNode == pHead){
preNode->next = nullptr;
currNode->next = preNode;
}else{
currNode->next = preNode;
}
preNode = currNode;
currNode = tempNode;
}
pHead = preNode;
return pHead;
}
};
2）第一次遍历链表，将链表每个node的值（val）存入栈中。由于栈“后进先出”，再次遍历链表，并从数据中依此读取栈顶元素。注意pop()并不会返回元素，因此应该使用top()访问栈顶元素。 也可以在栈中存储节点 stack<ListNode*> saveNode;
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == nullptr)
return nullptr;
if(pHead->next == nullptr) //只有一个节点
return pHead;
ListNode* currNode = pHead;
stack<int> saveValued;
while(currNode!=nullptr){
saveValued.push(currNode->val);
currNode = currNode->next;
}
currNode = pHead;
while(currNode!=nullptr){
currNode->val = saveValued.top(); //访问栈顶元素
saveValued.pop(); //删除栈顶元素，并没有返回值
currNode = currNode->next;
}
return pHead;
}
};
3）用递归实现反转链表：
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == nullptr || pHead->next == nullptr)
return pHead;
ListNode* newHead = ReverseList(pHead->next);
pHead->next->next = pHead;
pHead->next = nullptr;
return newHead;
}
};
/*解析：当递归调用到pHead为最后一个节点时，返回pHead（尾节点）赋值给newHead。
即newHead指向尾节点。结束本次调用。
此时，返回到上一个节点的调用，即pHead为倒数第二个节点，
pHead->next->next = pHead;将其下一个节点的指针指向该节点
pHead->next = nullptr; 删除该节点向下一个节点的指针
直到递归结束，返回新的头节点即可
*/
原文：https://www.cnblogs.com/GuoXinxin/p/10449509.html