【转】链表的转向

链表的转向是常考的内容，方法也很多。

今天在网上看到一个最直观易懂的，摘录下来供大家参考下。

转自： http://blog.csdn.net/feliciafay/article/details/6841115

 

方法：使用3个指针遍历单链表，逐个链接点进行反转。

步骤：使用p和q两个指针配合工作，使得两个节点间的指向反向，同时用r记录剩下的链表。

p = head;

q = head->next;

 head->next = NULL;

 现在进入循环体，这是第一次循环。

r = q->next;

q->next = p;

p = q;

q =r;

第二次循环。

r = q->next

 q->next = p;  

p = q;

q = r

 第三次循环。。。。。

 

代码如下：

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