算法学习-单链表反转

单链表的反转是一道很基本的算法题，一般可以想到以下三种方法：

• 方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。
• 方法2：使用三个指针遍历单链表，逐个节点进行反转。
• 方法3：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，表的最后将第一个节点挪到新表尾。

第一种不太可取，主要看下第二种和第三种的实现。

方法二：

Node* ReverseList(Node *head)  
{  
    Node *p1,*p2,*p3;  
    if(head==NULL||*head==NULL)  
    {
        return head; 
    } 
    p1=head;  
    p2=p1->next;  
    while(p2)             //注意条件  
    {  
        p3=p2->next;       //要改变p2->next的指针，所以必须先保留p2->next           
        p2->next=p1;  
        p1=p2;            //循环往后  
        p2=p3;  
    }  
    head->next=NULL;   //原先的head已经变成tail，别忘了置空，只有到这步才能置空  
    *head=p1;  
    return head;  
} 

方法三：

Node* ReverseList(Node* head)   
{   
    Node *p,*q;    
    p=head->next;   
    while(p->next!=NULL)      //在这个循环过程中p所指的元素一直是不变的  
    {  
        q=p->next;   
        p->next=q->next;   
        q->next=head->next;   
        head->next=q;   
    }    
    p->next=head;            //相当于成环   
    head=p->next->next;       //新head变为原head的next   
    p->next->next=NULL;     //断掉环   
    return head;     
}