看图深入理解单链表的反转-创新互联
如何把一个单链表进行反转?
成都创新互联-专业网站定制、快速模板网站建设、高性价比石楼网站开发、企业建站全套包干低至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://scyanting.com/article/coejce.html