频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
C++中经典的单向链表反转
2012-11-14 14:33:31           
收藏   我要投稿

 1 struct linka {
 2 int data;
 3 linka* next;
 4 };
 5 void reverse(linka*& head) {
 6 if(head ==NULL)
 7     return;
 8 linka *pre, *cur, *ne;
 9 pre=head;
10 cur=head->next;
11 while(cur)
12 {
13    ne = cur->next;
14    cur->next = pre;
15    pre = cur;
16    cur = ne;
17 }
18 head->next = NULL;
19 head = pre;
20 }
其中比较难理解的是linka*& head,传入的其实就是linka *的类型就可以了,linka *是表示linka类型的指针,&表示head的地址,也就是linka的指针www.2cto.com

另外需要熟悉的是head->next,其实有点像C#中的head.Next,就是structure中的一个属性.

首先定义3个指针,分别是前中后,然后当中间那个指针非空,就是当前不是空,就做循环里的事情

注意的是这个算法里面next是在循环里面赋值的

每次循环都把current指向previous了,然后大家都往后移一个,next=current->next必须在current改变方向之前做,否则改变了方向之后current的next就变成previous了。

最后跳出循环之后,将header的next首先置空,因为head变成了最后一个node了。然后head就变成了previous,因为当时 current和next都为NULL了,只有previous为最后一个节点(或者说这时候应该是第一个非空节点,也就是head)

终于把整个算法理解了一遍,最后想想其实挺简单,但是能用c++写出来也不太容易,特别是在面试的时候。

 

再增加一个递归的单链表反转的方法:


 1 static link ReverseLink3(link pNode)   // using recursion
 2         {
 3             if (pNode.next == null)
 4                 return pNode;
 5             link pNext = pNode.next;
 6             link head = ReverseLink3(pNext);
 7             pNext.next = pNode;
 8             pNode.next = null;
 9             return head;
10         }

点击复制链接 与好友分享!回本站首页
相关TAG标签 C++ 单向 经典
上一篇:C++使用Uniscribe进行文字自动换行的计算和渲染
下一篇:C++模板会使代码膨胀吗
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站