反转单链表的方法

方法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;// 返回当前节点  
}