给出一个链表的头结点，将链表反转后返回新的头结点
首先假设该链表头结点【pHead】在左边，尾节点在右边
设定三个指针:tmp 、p、q
其中tmp和q两个指针将不断向后移动，而p指针则定在原头结点位置不动，但其next将不断跟着tmp和q指针移动。
tmp q
@ ——> @ ——> @ ——> @ ——> @ 初始状态
p
第一步我们改变p指针的Next，使其指向p的next，并将q指针的next反转到tmp上
tmp q
/```````````
@ <—— @ @ ——> @ ——> @ 第一步
p
第二步将tmp指针移动到q指针的位置，并将q指针移动到p->next的位置
tmp q
/```````````
@ <—— @ @ ——> @ ——> @ 第二步
p
此时我们发现已经出现了初始状态的情况，重复做第一步
继续将p->next指向q->next，并反转q->next的指针到tmp上
tmp q
/``````````````````
@ <—— @ <—— @ @ ——> @ 第一步
p
继续将tmp和q指针向后移动，相当于重复做第二步
tmp q
/``````````````````
@ <—— @ <—— @ @ ——> @ 第二步
p
重复第一步
tmp q
/`````````````````````````
@ <—— @ <—— @ <—— @ @ 第一步
p
继续将tmp指针和q指针后移
tmp q
/`````````````````````````
@ <—— @ <—— @ <—— @ @ 第二步
p
此时发现，我们已经将p指针挪到了链表尾部，q->next为空，那么正好将p直接指向q的next，使其为NULL，由原头结点变为尾节点，而因为q指针指向节点的next反转到tmp上，最后一个节点的指针也反转过来了，新的头结点诞生。
而因为q不能继续后移到空指针上，因此while循环退出，tmp正常后移到q节点上，返回tmp指针即反转后的头结点指针。【此处明明tmp和q指针指向相同的位置，为什么返回的是tmp指针？ 因为在链表只有一个节点时，q是空指针，而tmp是头结点，那么反映了一种情况即，只有一个节点，头结点即尾节点，反转后不变，循环不进入，直接返回初始tmp,也就是头结点，而q指针就不同了，其指向的是空指针，从未指向头结点，因此不能返回q指针而应返回tmp】
NULL tmp
↑ q
@ <—— @ <—— @ <—— @ <—— @ 第二步
p
代码如下：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL)return pHead;
ListNode* p=pHead;
ListNode* q=pHead->next;
ListNode* tmp=pHead;
while(p->next!=NULL)
{
p->next=q->next;
q->next=tmp;
tmp=q;
if(p->next==NULL)break;
q=p->next;
}
return tmp;
}
};
另一种写法，最普遍的三指针法。也是很好理解的：
当前结点的下一个即pNext
当前结点的前一个即pPrev
当前结点即pNode
将当前结点的下一个存下来，判断是否为空，则可知当前结点是不是翻转后链表的首节点
将当前节点的m_pNext指针指向上一个节点pPrev，将上一个节点指针指向后挪到当前结点，将当前结点指针指向下一个结点，重复以上步骤
ListNode* ReverseList(ListNode* pHead)
{
ListNode* pRevesedHead=nullptr;
ListNode* pNode=pHead;
ListNode* pPrev=nullptr;
while(pNode!=nullptr)
{
ListNode* pNext=pNode->m_pNext;
if(pNext==nullptr)pRevesedHead=pNode;
pNode->m_pNext=pPrev;
pPrev=pNode;
pNode=pNext;
}
return pRevesedHead;
}