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

时间:2022-05-29 19:43:25


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