方法1：
将单链表储存为数组，然后按照数组的索引逆序进行反转。
比较浪费空间
时间复杂度：O(N)
空间复杂度：O(N)
方法2：
使用3个指针遍历单链表，逐个链接点进行反转。
时间复杂度：O(N)
空间复杂度：O(1)
3-1.png
3-2.png
3-3.png
ActList* ReverseList2(ActList* head)
{
//ActList* temp=new ActList;
if(NULL==head|| NULL==head->next) return head; //少于两个节点没有反转的必要。
ActList* p;
ActList* q;
ActList* r;
p = head;
q = head->next;
head->next = NULL; //旧的头指针是新的尾指针，next需要指向NULL
while(q){
r = q->next; //先保留下一个step要处理的指针
q->next = p; //然后p q交替工作进行反向
p = q;
q = r;
}
head=p; // 最后q必然指向NULL，所以返回了p作为新的头指针
return head;
}
方法3：
从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。
时间复杂度：O(N)
空间复杂度：O(1)
插入到头结点之前.gif
//while循环版
void reverse(node*& head)
{
if ( (head == 0) || (head->next == 0) ) return;// 边界检测
node* pNext = 0;
node* pPrev = head;// 保存链表头节点
node* pCur = head->next;// 获取当前节点
while (pCur != 0)
{
pNext = pCur->next;// 将下一个节点保存下来
pCur->next = pPrev;// 将当前节点的下一节点置为前节点
pPrev = pCur;// 将当前节点保存为前一节点
pCur = pNext;// 将当前节点置为下一节点
}
head->next = NULL;
head = pPrev;
p;}
//递归版
node* reverse( node* pNode, node*& head)
{
if ( (pNode == 0) || (pNode->next == 0) ) // 递归跳出条件
{
head = pNode; // 将链表切断，否则会形成回环
return pNode;
}
node* temp = reserve(pNode->next, head);// 递归
temp->next = pNode;// 将下一节点置为当前节点，既前置节点
return pNode;// 返回当前节点
}
