当前位置：新励学网 > 建筑专业 > 单链表就地逆置有几种方法

单链表就地逆置有几种方法

发表时间：2024-07-22 12:00:54 来源：网友投稿

单链表就地逆置的两种(递归与普通循环) 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;}

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！