一个单链表，长度未知，如何快速的找出位于中间的那个元素？ 第1页
1
Ivony 网友的相关建议:
程序员看到算法就容易High起来，但老实说外行看热闹，内行看门道。我一直觉得算法这个东西用什么精妙来形容，算得上是外行看热闹。
在这个问题的答案下，有两个算法：
分别是
@蔡啸和
@Irons Du提供的，很显然前者的算法看起来比较精妙，而后者的算法看起来简直就是low爆了。
但事实上，不考虑vector扩容开销的话，这俩算法的时间复杂度都是O(n)，前者的优势在于其只需要俩指针空间，后者则直接把整个链表变成了一个vector，
也就是说后者是用空间换时间。
所以说这个看似很low的算法也是有其意义的，因为这个很low的算法通过指针获取元素的次数只有n+1或n次，而前者则需要获取n+n/2次。
当然，我们知道通过指针获取元素的性能是极高的，而且，1.5n和n+1的时间复杂度都是O(n)。但是如果通过指针获取元素的性能变得极差的时候（例如根本就是个远程调用的话），那么这种low爆的算法就会摇身一变成为最精妙的算法，而原来精妙的算法又会变为最SB的做法了。
算法没有高下之分，场景才是最重要的。
一个程序员成熟的标志就是从看到算法就会high，到看到薪酬才会high，，XD，，，，
1
相关话题
EM算法存在的意义是什么？一个单链表，长度未知，如何快速的找出位于中间的那个元素？
链表和数组的插入删除时间复杂度都是o(n)，为什么教材网络上说链表效率高？
链表和数组的插入删除时间复杂度都是o(n)，为什么教材网络上说链表效率高？
有哪些手算对数的方法？
经过足够长的时间， AlphaGo 的棋谱能收敛到一张上吗？
怎样将一个24的n次方复杂度的计算优化?
如果“P=NP”得到证明，意味着什么？
经过足够长的时间， AlphaGo 的棋谱能收敛到一张上吗？
百度识图是什么工作原理？
前一个讨论
女性该为自己穿得少招惹了色狼而负一定责任吗？
下一个讨论
这种水果有类似菠萝和芒果的味道，是什么水果？
相关的话题
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？有没有可能让计算机去理解代码，从而写代码？
如何直接跳出深层递归而不是一层一层跳出？
普通人如何对抗算法，从而避免信息茧房？
给人指路，说左右和说东西南北在算法上哪个更优？
算法源于大数据，而大数据源于我们每一个人，那我们是不是应该拥有主导数据的权利？
未来会不会有一种方式，可以使一部蓝光电影压缩到几Mb甚至几Kb？
参加 ACM-ICPC World Final 是怎样一种体验？
什么是机器学习？
报了蓝桥杯比赛，几乎零基础，如何准备，请大牛指导一下。谢谢？
如何看待阿里 P8 加面 coding 环节，而 P7 却做不出头条算法题？
如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明?
是否存在仅由1和2组成的长度为2^n的序列，可以做到在这个序列中取出所有含1和2的长度为n的序列？
这个号称「微软的面试题」，该如何解答？
N个互异数随机组成的数组的逆序数的分布公式是什么？
为什么同样是解决一个问题，别人就能想出算法，而我却绞尽脑汁，百般尝试也不得其法？
有哪些你看了以后大呼过瘾的编程书？
比特币的算法到底在算什么？
算法研究属于数学专业还是计算机专业？
哪位大佬能来个骨灰级的红黑树讲解啊？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
如何看待王思聪开始第二波抽奖，这轮抽奖结果的性别比是否会发生明显的变化？
计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？
Linear least squares, Lasso,ridge regression有何本质区别？
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？
如何看待阿里 P8 加面 coding 环节，而 P7 却做不出头条算法题？
什么是哈希洪水攻击（Hash-Flooding Attack）？
为什么同样是解决一个问题，别人就能想出算法，而我却绞尽脑汁，百般尝试也不得其法？
Auto X的自动驾驶技术用了什么技术？
如果一个算法空间复杂度是指数级，时间复杂度是多项式级，那么这个算法复杂度怎么算呢？