LeetCode--初级算法--反转链表

参考：反转链表的方法
反转一个单链表。

示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

分析：

反转单链表的方法：
方法1：
将单链表储存为数组，然后按照数组的索引逆序进行反转。
比较浪费空间
时间复杂度：O(N)
空间复杂度：O(N)

方法2：
使用3个指针遍历单链表，逐个链接点进行反转。
时间复杂度：O(N)
空间复杂度：O(1)

代码：

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;      
}