一年十二月  谁主春秋
关注:基础系统工程 密码学 人工智能
C++博客
首页
新随笔
联系
聚合
管理
随笔-152 评论-223 文章-30 trackbacks-0
求单向链表倒序第m个元素
原题为某游戏公司试题,大意如下:
对于一个单向链表,试写出找到它的倒序第m
个元素(m >= 1)的函数,注意变量命名、注释、时间复杂度、空间复杂度。
注:要求写出可编译并可以运行通过的程序代码。
这道题的常规做法或者说首先想到直觉的方法M1是先求得链表的长度,即元素总个数n,然后问题转化为求顺序第n-m+1个元素。下面给出第2种方法M2:先求得顺序第m个元素,用一指针P指向这个元素,用另一指针PR指向链表的头部,现在好了,P和PR同时向右移动,直到P为空,则PR就是要求的倒序第m个元素,如果因m超越界限,则PR为空,表示没找到,这样一来,只需一次循环就够了。C++代码描述如下
1
template
<
typename T
>
2
struct
Node
3
{
4
T data;
/**/
/**/
/**/
///
< 数据
5
Node* next;
///
< 指向下一结点的指针
6
} ;
7
8
template
<
typename T
>
9
Node
<
T
>*
ReverseFind(Node
<
T
>*
head, size_t m)
10
{
11
size_t n
=
0
;
12
Node
<
T
>
*
p,
*
pR
=
NULL;
13
for
(p
=
head;p;p
=
p
->
next)
14
{
15
if
(
++
n
==
m)
16
{
17
pR
=
head;
18
continue
;
19
}
20
if
(pR)
21
{
22
pR
=
pR
->
next;
23
}
24
}
25
return
pR;
26
}
现在分析这2种方法的时间复杂度,假设链表元素个数为N,所求倒序为第M元素,N>=M,则M1方法为0(N)+0(N-M)=0(2N-M),M2方法为O(M)+O(N-M)=0(N),因此M2快于M1。
posted on 2011-06-24 11:40
春秋十二月
阅读(2490)
评论(11)
编辑
收藏
引用
所属分类:
Algorithm
评论:
#
re: 求单向链表倒序第m个元素 2011-06-24 12:30 |
coreBugZJ
赞一个
回复
更多评论
#
re: 求单向链表倒序第m个元素 2011-06-24 16:45 |
paw
额,,考研数据结构题。。。
回复
更多评论
#
re: 求单向链表倒序第m个元素 2011-06-24 23:57 |
鱼吃猫
顶一个~
回复
更多评论
#
re: 求单向链表倒序第m个元素[未登录] 2011-06-25 12:06 |
英雄哪里出来
不错,赞一个~~
回复
更多评论
#
re: 求单向链表倒序第m个元素[未登录] 2011-06-25 13:39 |
kaka
第一个指针从头移动到m,和第二个指针一起再移动到尾部。
第二个指针和第一个指针一起移动。
只不过将一个指针大于一次遍历的操作分解成两个指针操作。
这样算是一次遍历?
回复
更多评论
#
re: 求单向链表倒序第m个元素 2011-06-25 23:36 |
梦提
是一次遍历,因为时间上是同步的。@kaka
回复
更多评论
#
re: 求单向链表倒序第m个元素 2011-06-26 08:47 |
搞笑
这个也太搞笑了?效率是一样的,还竟然有:“这样效率不高”的说法。
回复
更多评论
#
re: 求单向链表倒序第m个元素 2011-06-26 13:54 |
temp
是一样的,两个指针分别遍历。
回复
更多评论
#
re: 求单向链表倒序第m个元素 2011-06-26 15:24 |
Arcko
貌似需要遍历的确实是一样的多,不过换个思路考虑也很好
回复
更多评论
#
re: 求单向链表倒序第m个元素 2011-06-27 10:09 |
megadeath
使用递归方式(示例代码,无任何错误检查),把for语句也消隐掉。
static int nOrder = 0;
template <typename ITERATOR, typename UINT>
void F(ITERATOR begin, ITERATOR end, UINT M)
{
ITERATOR it = begin;
if (begin != end)
F(++begin, end, M);
if (++nOrder == ++M)
cout << *it << endl;
}
回复
更多评论
#
re: 求单向链表倒序第m个元素
2011-07-01 11:06 |
有雾
我也感觉效率一样的。第二个里面,同样要把P移动到链表尾,这样才能获得size。所以不存在O(M),同样是O(N)啊。@搞笑
回复
更多评论
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
简单私钥加密构造的验证及安全性分析
二元有限域及其扩域上的计算
简单连分数攻击RSA的迭代次数分析
有限循环群的结构及生成元的判定
混合线性同余发生器的引理验证
Blum数的基本定理及应用
一个积分攻击定理的证明
浅谈对称加密算法的软件实现
浅谈密码学几点安全性分析
AES不可约多项式
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
本博客所有随笔均为原创,因为不定期维护更新,所以转载请注明出处,如有问题和建议,请留言或评论,发表您的宝贵意见,藉此平台以分享交流、共同进步。
联系方式:微信theory-math
<
2013年9月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(62)
给我留言
查看公开留言
查看私人留言
随笔分类
(151)
Algorithm(39)
C/C++(24)
Compiler(25)
Compute Theory(5)
Database(4)
Network(17)
Opensrc(13)
System(24)
随笔档案
(152)
2024年6月 (1)
2024年5月 (1)
2024年4月 (1)
2024年3月 (2)
2024年2月 (2)
2023年12月 (1)
2023年11月 (2)
2023年10月 (2)
2023年9月 (37)
2021年12月 (1)
2021年10月 (1)
2021年9月 (1)
2021年2月 (1)
2020年5月 (3)
2020年4月 (1)
2019年11月 (4)
2019年7月 (1)
2018年11月 (1)
2017年12月 (1)
2016年12月 (1)
2016年11月 (2)
2016年10月 (1)
2016年9月 (1)
2016年8月 (3)
2016年7月 (4)
2016年5月 (1)
2015年10月 (2)
2015年9月 (1)
2015年6月 (2)
2015年5月 (3)
2015年2月 (1)
2015年1月 (1)
2014年12月 (2)
2014年4月 (2)
2014年3月 (1)
2014年1月 (1)
2013年10月 (1)
2013年9月 (1)
2013年8月 (3)
2013年5月 (1)
2013年3月 (1)
2012年11月 (1)
2012年9月 (3)
2012年8月 (1)
2012年7月 (1)
2012年6月 (5)
2012年5月 (3)
2011年12月 (5)
2011年11月 (1)
2011年10月 (5)
2011年8月 (7)
2011年7月 (6)
2011年6月 (6)
2010年6月 (1)
2009年12月 (1)
2009年8月 (1)
2009年7月 (1)
2009年6月 (1)
2009年4月 (3)
文章分类
(30)
诗词作品集(30)
关注的开源项目
LLVM
编译系统
nginx
高性能Web服务器
OpenSSL
密码学库
suricata
网络IPS引擎
最新随笔
1. 简单私钥加密构造的验证及安全性分析
2. 二元有限域及其扩域上的计算
3. 简单连分数攻击RSA的迭代次数分析
4. 有限循环群的结构及生成元的判定
5. 混合线性同余发生器的引理验证
6. Blum数的基本定理及应用
7. 关于(零知识)计算复杂性的总结
8. 一个积分攻击定理的证明
9. 浅谈体系结构与内联优化
10. 浅谈对称加密算法的软件实现
积分与排名
积分 - 397443
排名 - 58
最新评论
1. re: 一种拦截Linux原始套接字IO的方法[未登录]
很有前途和很有钱途啊。
--chipset
2. re: 一种拦截Linux原始套接字IO的方法[未登录]
@chipset
是的
--春秋十二月
3. re: 一种拦截Linux原始套接字IO的方法[未登录]
工作是做网络安全?
--chipset
4. re: 一种使用函数指针实现状态机的方法
函数指针实现状态机
--linda
5. re: 多标签视图类CTabView的设计实现
为啥代码缺少一些呢,给新手个完整点的啊
--pekingliu
6. re: 工作线程与消息循环
从消息队列取出消息 mark了
--mmocake
7. re: 一种简单的跨平台套接字管道
评论内容较长,点击标题查看
--IT搬运工
8. re: 一种简单的跨平台套接字管道
windows仅支持af_init和af_init6地址族有错别字么?
af_init和af_init6
--IT搬运工
9. re: Shell应用(8):使用awk定位反汇编输出[未登录]
厉害
--Chipset
10. re: TCP分组丢失时的状态变迁
不错
--Binky
阅读排行榜
1. 基于OpenSSL实现的安全连接(13646)
2. 字符串16进制显示(12778)
3. 基于boost asio实现的ssl socket框架(12139)
4. Linux套接字与虚拟文件系统(1):初始化和创建(8506)
5. 关于数据库的一些学习研究心得(8030)
6. 使用CString GetBuffer自适应获取计算机名称(7912)
7. 使用正则表达式解析URL(7789)
8. basic_string内存泄露问题之分析解决(7597)
9. Shell应用(4): 使用sed删除行尾的^M字符(7530)
10. nginx iocp(1):tcp异步连接(7439)
评论排行榜
1. basic_string内存泄露问题之分析解决(19)
2. 求单向链表倒序第m个元素(11)
3. 基于顺序存储实现的多叉树(1):深度优先存储(9)
4. 字符大小写转换(7)
5. 面向对象锁框架的设计与实现(6)
6. 字符串16进制显示(6)
7. 工作线程与消息循环(5)
8. Shell应用(4): 使用sed删除行尾的^M字符(5)
9. 使用正则表达式解析URL(5)
10. 十进制整数千位分隔符(4)