Question

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

Answer 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;    　　//返回新的子序列的头结点

}

二、用普通算法循环逆置（头插法重新建立带头结点的新链表）

参考链接：https://blog.csdn.net/onlyoncelove/article/details/81988514