- 浏览: 92204 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
zhanglufei2010:
还有一个方法可行:直接将site-1.6.16.zip解压后的 ...
SVN与MYECLIPSE8.6
扩展问题1:查找单向链表中的倒数第k个节点。
思路:按照遍历查找链表的常用模式,可能会马上想到一种简单的方法就是:先遍历链表,看一下链表中有多少个节点。假设链表中有n个节点,那么要找倒数第k个,也就是正数n-k+1个了。接下来,只要指针从头向后走n-k步就可了。这种方法大约要执行2n-k次。
那么,有没有比上面的方法更高效的方法呢?把思维打开,不要固定在遍历链表的时候只能用有一个指针的思维定式上。我们可以尝试用多个指针以不同的次序开始遍历链表。
对于,这个问题,我们就可以设置两个指针,一个指针先在链表上走K步,然后另一个指针从链表头开始和前一个指针一起向后走,这样当第一个指针到达链表尾部时候,第二个指针就会在第一个指针前面k个结点处。这时就找到了倒数第K个节点,算法执行的次数为n 次,比上一个方法减少了一些步,如图4。
图4 查找倒数第k个节点
代码实现:
gleList* returnNodeFromBack(SingleList* head,int k)
//返回链表中的倒数第K节点的指针//输入参数:单链表的头指针,要查找的节点的倒数位置//输出参数:无//返回值:成功返回节点指针,失败返回NULLSingleList* returnNodeFromBack(SingleList* head,int k){ SingleList *firstPtr,*secondPtr; int count = 0; firstPtr = secondPtr = head; while((firstPtr)&&(count < k)) { firstPtr = firstPtr->next; count++; } if(count < k) { return NULL; } while(firstPtr) { firstPtr = firstPtr->next; secondPtr = secondPtr->next; } return secondPtr;}扩展问题2:查找单向链表中的中间节点,当节点个数为偶数时返回中间两个元素中的前者(后者)
思路:类似于第一个扩展问题,对于查找中间元素,我们首先也可以利用先遍布链表看一看总共有多少个节点,然后再走节点总个数的一半即可找到中间元素。显然,这种方法也是要遍历两次链表。
那么,能不能借鉴上面的改进方法再来改进一下这个问题呢。当然可以,在此问题中依然使用两个遍历指针。让第一个指针每次走两步,第二个指针每次走一步,这样因为第一个指针经过的节点数是第二指针的两倍,所以当第一个指针到达中点时,第二个指针正好处于链表的中间位置。
代码实现:
SingleList* returnMidNode(SingleList* head)
//返回链表的中间节点//输入参数:单链表的头指针//输出参数:无//返回值:中间节点的指针或NULLSingleList* returnMidNode(SingleList* head){ SingleList *firstPtr,*secondPtr; firstPtr = secondPtr = head; //链表中没有节点或只有一个节点 if((firstPtr == NULL) || (firstPtr->next == NULL)) { return firstPtr; } //while((firstPtr)&&(firstPtr->next)) //偶数个数时返回中间两个索引较大者 while((firstPtr->next)&&(firstPtr->next->next))//偶数个数时返回中间两个索引较小者 { firstPtr = firstPtr->next->next; secondPtr = secondPtr->next; } return secondPtr;}
扩展问题:返回两个链表的第一个交点?
仔细阅读上一个问题的思路,可发现思路中第一种解决方法就可以解决这个问题。但其时间的复杂度为O(n2)。那么能不能仿照第二种方法一样来提高算法的效率呢?答案,当然是可以。
分析两个相交链表的性质可知,如果相交,则交点之后的链表节点同时属于这两个链表。由此可以推断出,交点之后每条链表上节点的个数肯定是相同的。因此,如果两条链表节点的个数分别为len1和len2(len1>len2),那么他们的第一个交点在第一条链表上肯定是第(len1-len2)个节点之后的某个节点。
总结上面的分析,我们得出一算法:
(1)先分别遍历一遍两条链表,求出两链表各自的节点个数len1和len2。
(2)让节点多的链表先走|len1-len2|
(3)两条链表同时向后步进,并判断节点是否相同。第一个相同点就是第一个交点。
代码实现:
view sourceprint?01 //求两条单向链表的第一个交点
02 //输入参数:两个单链表的头指针
03 //输出参数:无
04 //返回值:相交返回第一个交点指针,不相交返回NULL
05 SingleList* FirstIntersectNode(SingleList *head1,SingleList *head2)
06 {
07 SingleList *firstPtr = head1,*secondPtr = head2;
08 int len1 = 0,len2 = 0;
09
10 //循环遍历第一个链表
11 while(firstPtr)
12 {
13 firstPtr = firstPtr->next;
14 len1++;
15 }
16
17 //循环遍历第二个链表
18 while(secondPtr)
19 {
20 secondPtr = secondPtr->next;
21 len2++;
22 }
23
24 firstPtr = head1;
25 secondPtr = head2;
26
27 //让指向较长链表的指针,先走出长出的几步
28 if(len1 > len2)
29 {
30 for(int i=0; i < (len1-len2);i++)
31 {
32 firstPtr = firstPtr->next;
33 }
34 }
35 else
36 {
37 for(int i=0; i < (len2-len1);i++)
38 {
39 secondPtr = secondPtr->next;
40 }
41 }
42 while(firstPtr&&secondPtr)
43 {
44 if(firstPtr == secondPtr)
45 {
46 return firstPtr;
47 }
48 firstPtr = firstPtr->next;
49 secondPtr = secondPtr->next;
50 }
51 return NULL;
52 }
思路:按照遍历查找链表的常用模式,可能会马上想到一种简单的方法就是:先遍历链表,看一下链表中有多少个节点。假设链表中有n个节点,那么要找倒数第k个,也就是正数n-k+1个了。接下来,只要指针从头向后走n-k步就可了。这种方法大约要执行2n-k次。
那么,有没有比上面的方法更高效的方法呢?把思维打开,不要固定在遍历链表的时候只能用有一个指针的思维定式上。我们可以尝试用多个指针以不同的次序开始遍历链表。
对于,这个问题,我们就可以设置两个指针,一个指针先在链表上走K步,然后另一个指针从链表头开始和前一个指针一起向后走,这样当第一个指针到达链表尾部时候,第二个指针就会在第一个指针前面k个结点处。这时就找到了倒数第K个节点,算法执行的次数为n 次,比上一个方法减少了一些步,如图4。
图4 查找倒数第k个节点
代码实现:
gleList* returnNodeFromBack(SingleList* head,int k)
//返回链表中的倒数第K节点的指针//输入参数:单链表的头指针,要查找的节点的倒数位置//输出参数:无//返回值:成功返回节点指针,失败返回NULLSingleList* returnNodeFromBack(SingleList* head,int k){ SingleList *firstPtr,*secondPtr; int count = 0; firstPtr = secondPtr = head; while((firstPtr)&&(count < k)) { firstPtr = firstPtr->next; count++; } if(count < k) { return NULL; } while(firstPtr) { firstPtr = firstPtr->next; secondPtr = secondPtr->next; } return secondPtr;}扩展问题2:查找单向链表中的中间节点,当节点个数为偶数时返回中间两个元素中的前者(后者)
思路:类似于第一个扩展问题,对于查找中间元素,我们首先也可以利用先遍布链表看一看总共有多少个节点,然后再走节点总个数的一半即可找到中间元素。显然,这种方法也是要遍历两次链表。
那么,能不能借鉴上面的改进方法再来改进一下这个问题呢。当然可以,在此问题中依然使用两个遍历指针。让第一个指针每次走两步,第二个指针每次走一步,这样因为第一个指针经过的节点数是第二指针的两倍,所以当第一个指针到达中点时,第二个指针正好处于链表的中间位置。
代码实现:
SingleList* returnMidNode(SingleList* head)
//返回链表的中间节点//输入参数:单链表的头指针//输出参数:无//返回值:中间节点的指针或NULLSingleList* returnMidNode(SingleList* head){ SingleList *firstPtr,*secondPtr; firstPtr = secondPtr = head; //链表中没有节点或只有一个节点 if((firstPtr == NULL) || (firstPtr->next == NULL)) { return firstPtr; } //while((firstPtr)&&(firstPtr->next)) //偶数个数时返回中间两个索引较大者 while((firstPtr->next)&&(firstPtr->next->next))//偶数个数时返回中间两个索引较小者 { firstPtr = firstPtr->next->next; secondPtr = secondPtr->next; } return secondPtr;}
扩展问题:返回两个链表的第一个交点?
仔细阅读上一个问题的思路,可发现思路中第一种解决方法就可以解决这个问题。但其时间的复杂度为O(n2)。那么能不能仿照第二种方法一样来提高算法的效率呢?答案,当然是可以。
分析两个相交链表的性质可知,如果相交,则交点之后的链表节点同时属于这两个链表。由此可以推断出,交点之后每条链表上节点的个数肯定是相同的。因此,如果两条链表节点的个数分别为len1和len2(len1>len2),那么他们的第一个交点在第一条链表上肯定是第(len1-len2)个节点之后的某个节点。
总结上面的分析,我们得出一算法:
(1)先分别遍历一遍两条链表,求出两链表各自的节点个数len1和len2。
(2)让节点多的链表先走|len1-len2|
(3)两条链表同时向后步进,并判断节点是否相同。第一个相同点就是第一个交点。
代码实现:
view sourceprint?01 //求两条单向链表的第一个交点
02 //输入参数:两个单链表的头指针
03 //输出参数:无
04 //返回值:相交返回第一个交点指针,不相交返回NULL
05 SingleList* FirstIntersectNode(SingleList *head1,SingleList *head2)
06 {
07 SingleList *firstPtr = head1,*secondPtr = head2;
08 int len1 = 0,len2 = 0;
09
10 //循环遍历第一个链表
11 while(firstPtr)
12 {
13 firstPtr = firstPtr->next;
14 len1++;
15 }
16
17 //循环遍历第二个链表
18 while(secondPtr)
19 {
20 secondPtr = secondPtr->next;
21 len2++;
22 }
23
24 firstPtr = head1;
25 secondPtr = head2;
26
27 //让指向较长链表的指针,先走出长出的几步
28 if(len1 > len2)
29 {
30 for(int i=0; i < (len1-len2);i++)
31 {
32 firstPtr = firstPtr->next;
33 }
34 }
35 else
36 {
37 for(int i=0; i < (len2-len1);i++)
38 {
39 secondPtr = secondPtr->next;
40 }
41 }
42 while(firstPtr&&secondPtr)
43 {
44 if(firstPtr == secondPtr)
45 {
46 return firstPtr;
47 }
48 firstPtr = firstPtr->next;
49 secondPtr = secondPtr->next;
50 }
51 return NULL;
52 }
发表评论
-
oracle 环境变量设置
2016-11-15 16:28 819转发的 http://spryingf.blog.163.co ... -
Oracle 用户锁表解决办法
2016-09-14 13:52 4581. 查看被锁的表 SELECT p.spid, ... -
Oracle 新建用户赋权
2016-07-05 17:56 571grant create session to eosccb; ... -
JSP导出excel
2016-03-14 17:54 792jsp导出excel文件并设定单元格格式 原文地址 http ... -
JS常用方法总结
2016-02-17 09:26 750function trimStr(str){ return ... -
tomcat中jndi配置
2016-02-02 15:08 537结合tomcat配置,3种配置方式 1)全局配置,tomcat ... -
maven相关
2015-10-20 20:41 979Class "" is listed in ... -
linux相关
2015-10-13 13:47 326输入"uname -a ",可显示电脑以及 ... -
tomcat linux启动
2015-10-13 12:42 503-bash: ./startup.sh: Permission ... -
mysql命令
2015-10-09 16:43 301mysql创建数据库带指定编码: CREATE DATABAS ... -
Eclipse SVN插件离线安装
2015-09-23 16:54 4721将site-1.6.18.zip下载。 然后再eclipse ... -
mysql linux命令
2015-09-17 16:57 544比如我们要备份mysql中已经存在的名为linux的数据库,要 ... -
maven项目导入
2015-09-17 14:20 575之前自己新建过maven项目,这次是用别的项目直接使用 软件 ... -
websphere错误
2015-08-13 16:17 2280websphere Java虚拟机内存修改过大启动报错 解决 ... -
PHP STUDY
2015-07-29 10:16 531登录phpmyadmin提示: #1045 无法登录 MySQ ... -
测试要点
2015-07-27 15:01 265现在的项目有这样的问题,测试需要自己进行。在项目进行的 ... -
普元ESB学习
2015-07-24 13:54 473今天做了两个示例 1 HTTP穿透 建立公共模块,新建tr ... -
ESB 项目需求分析和方案设计浅谈(复制转载)
2015-07-24 09:09 772找到一篇非常好的文章,为了防止以后博主删除文章看不到了,所以完 ... -
第一个项目管理的总结
2015-07-23 16:41 563经历了自己第一个项目的管理和上线,有许多的不足和问题, ... -
ESB学习
2015-07-23 15:56 382百度百科的定义: ESB全称为Enterprise ...
相关推荐
267 6.5 复制文件 268 实例186 移动正在使用的文件 268 实例187 批量复制文件 269 6.6 指定类型的文件操作 270 实例188 文本文件的操作 270 实例189 简单的文件加密解密 271 6.7 ...
27 <br>0056 强行改变运算符的运算顺序 27 <br>第3章 程序算法 29 <br>3.1 数据结构 30 <br>0057 如何实现单向链表 30 <br>0058 如何实现双向链表 35 <br>0059 如何实现堆栈 41 ...
实例198 创建单向链表 282 实例199 创建双向链表 284 实例200 创建循环链表 287 实例201 使用头插入法建立单链表 289 实例202 双链表逆序输出 291 实例203 约瑟夫环 293 实例204 创建顺序表并插入元素 294 实例205 ...
左程云《程序员代码面试指南》第二版编程题的Python语言实现 牛客网OJ: LeetCode: 1、故下面除特殊说明,否则OJ链接均默认为LeetCode对应题目链接。因为牛客网OJ在链表、二叉树等相关题目均把题目数据以链表数据...
实例131 单向链表的实现 164 实例132 双向链表的实现 168 实例133 堆栈的实现 173 实例134 队列的实现 175 实例135 树的实现 177 6.2 常见算法的实际应用 180 实例136 计算1+22+33+44+…+nn的值 180 实例137 计算10...
1.6 特殊形状的窗体 26 实例021 非矩形窗体 26 实例022 建立字体形状窗体 28 1.7 多媒体光盘 29 实例023 自动启动的多媒体光盘程序 29 实例024 为触摸屏程序添加虚拟键盘 30 实例025 触摸屏系统 31 ...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...