资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

看图深入理解单链表的反转-创新互联

如何把一个单链表进行反转?

成都创新互联-专业网站定制、快速模板网站建设、高性价比石楼网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式石楼网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖石楼地区。费用合理售后完善,十载实体公司更值得信赖。

方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。

方法2:使用3个指针遍历单链表,逐个链接点进行反转。

方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾。

方法4:   递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑用递归来解决。但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归来解决。或者说,因为单链表本身的结构也有自相似的特点,所以可以考虑用递归来解决)

方法1:

浪费空间。

方法2:

使用p和q两个指针配合工作,使得两个节点间的指向反向,同时用r记录剩下的链表。

p = head;

q = head->next;

看图深入理解单链表的反转

head->next = NULL;

看图深入理解单链表的反转

现在进入循环体,这是第一次循环。

r = q->next;

q->next = p;

看图深入理解单链表的反转

p = q;

q =r;

看图深入理解单链表的反转

第二次循环。

r = q->next

看图深入理解单链表的反转

q->next = p;

看图深入理解单链表的反转

p = q;

看图深入理解单链表的反转

q = r

看图深入理解单链表的反转

第三次循环。。。。。

具体代码如下

ActList* ReverseList2(ActList* head)
{
	//ActList* temp=new ActList;
 if(NULL==head|| NULL==head->next) return head; //少于两个节点没有反转的必要。
 ActList* p;
	ActList* q;
	ActList* r;
 p = head; 
 q = head->next;
 head->next = NULL; //旧的头指针是新的尾指针,next需要指向NULL
 while(q){
 r = q->next; //先保留下一个step要处理的指针
 q->next = p; //然后p q交替工作进行反向
 p = q; 
 q = r; 
 }
	head=p; // 最后q必然指向NULL,所以返回了p作为新的头指针
 return head; 
}

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


名称栏目:看图深入理解单链表的反转-创新互联
转载注明:http://www.cdkjz.cn/article/coejce.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220