贡献者: 叶燊Leafshen
数组
我们最常做的就是遍历法了,简单,暴力,将遍历到的元素依次放入数组 A 中。如果我们遍历到了 n 个元素,那么链表及数组的长度也为 n,对应的中间节点即为 A[n/2]。
下面整理的为几种语言的部分代码:
python 如上 C++见上时间复杂度:O(N),其中 N 是给定链表中的结点数目。
空间复杂度:O(N),即数组 A 用去的空间。
单指针法
方法一可以进行空间优化,比如省去数组 A。
我们可以对链表进行两次遍历。第一次遍历时,我们统计链表中的元素个数 N;第二次遍历时,我们遍历到第 N/2 个元素(链表的首节点为第 0 个元素)时,返回该元素即可。
相当于,方法一我们拿刻度瓶装,方法二我们用数豆子的方法
python 如上 java 如上时间复杂度:O(N),其中 N 是给定链表的结点数目。
空间复杂度:O(1),常数空间存放变量和指针。
快慢指针法
继续优化,用两个速度不同的指针 slow 与 fast 一起遍历链表。速度不同产生位移之差,于是,我们让慢爷爷一次走一步,快小伙一次走两步。不妨试试,你会发现,当 fast 走到末尾时,slow 恰在中间。
所以:
python c++ java友情链接: 超理论坛 | ©小时科技 保留一切权利