单链表就地逆置的两种方法(递归与普通循环）



//1.用递归算法,对于不带头结点的单链表（a1,a2,a3,a4,a5,a6）逆置后的结果为（a6,a5,a4,a3,a2,a1）
//考虑递归算法，若只有一个结点，则直接返回，若存在两个结点（a1,a2）则需要做的操作有：　　　　　　a2->next=a1;a1->next=NULL;return a2;
//a2即新的头结点，若有三个结点,则应先将子链（a2,a3）先逆置且返回该子链的新的头结点，然后把子链（a2,a3）当作一个复合结点a2',
//组成新的二元组（a1,a2'）然后就可以执行前面相同的操作：a2'->next=a1;a1->next=NULL;return a3';即可，多个以上的结点可同理得到，
Node *Reverse(Node *head)
{
 Node *p=head;
 if(p==NULL)
  return NULL;　　　　　//若是空链表，返回空
 Node *q=p->next;
 if(q==NULL)
  return p;　　　　　//若只有一个结点，直接返回
 else
 head=Reverse(q);　　//记录子序列的新的头结点
 q->next=p;　　　　　//当前结点与已经逆置的子序列看成是前后的两个结点p,q，作相应的逆置操作
 p->next=NULL;
 return head;    　　//返回新的子序列的头结点
}
//2.用普通算法循环逆置（头插法重新建立带头结点的新链表）
Node *Reverse(Node *head)
{
 Node *p=head->next;
    if(p)//若链表不为空，则逆置，否则，空操作
 {
  　Node *q=p->next;
 　　head->next=NULL;//头结点分离
 　　while(p)
 　　{
  　　p->next=head->next;　//头插法建立链表
  　　head->next=p;
  　　if(q)    //操作空指针的时候一定要非常注意，很容易出错
  　　{
   　　　p=q;
   　　　q=p->next;
  　　}
  　　else
   　　　break;
 　　}
 }

 return head;
}