2016 - 2024

感恩一路有你

单链表的就地逆置代码 单链表的就地逆置的算法?

浏览量:2199 时间:2021-03-14 02:39:02 作者:admin

单链表的就地逆置的算法?

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

两种单链表的局部反转(递归和普通循环)1。采用递归算法,对无前导节点的单链表(A1、A2、A3、A4、A5、A6)进行反向设置后得到(A6、A5、A4、A3、A2、A1)。考虑递归算法,如果只有一个节点,它将直接返回。如果有两个节点(A1,A2),则要执行的操作是:A2->next=A1,A1->next=NullReturn A2a2是新的头节点。如果有三个节点,则应首先反转子链(A2,A3),并返回子链的新头节点。然后将子链(A2,A3)看作一个复合节点A2”,形成一个新的二进制(A1,A2”),然后可以执行具有相同前面的操作:A2“->next=A1,A1->next=NullReturn A3”,即可以以相同的方式获得多个节点,node*reverse(node*head){node*P=head if(P==null)return null//如果是空链表,则返回一个空节点*q=P->next if(q==null)return P//如果只有一个节点,则返回else head=reverse(q)//记录子序列的新head q->next=P//将当前节点和反向子序列视为前后两个节点P、q。执行相应的反向操作p->next=null return head//返回新子序列的head节点}2。使用常用算法反向(head inserting method重建前导节点的新链表)node*reverse(node*head){node*P=head->next If(P)//如果链表不为空,则反向。否则,空操作{node*q=P->next head->next=null//头节点是分开的,而(P){P->next=head->next//在建立链表head->next=P if(q)//在操作空指针时,必须非常小心并且容易出错{P=q}q=P->next}否则break}return头}

例如,链表a-> B-> C-> D有头和尾。局部反转是指:a next=&BB->next=&CC->next=&DD->next=0反转后:B->next=&AC->next=&BD->next=&CA->next=0。所谓局部反转是指在操作过程中遇到a->next=&B时,将其重写为B->next=&a

单链表的就地逆置代码 单链表就地逆置算法 数据结构单链表逆置

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。