假设您希望尽可能高效地找到链表的中间节点。给出的最典型的“最佳”答案是保持2个指针，中间和当前。当遇到的元素数被2整除时，增加中间指针。因此，我们可以在1遍中找到中间值。高效，对吗？比蛮力更好，其中包括1次传递到最后，然后再传1次直到我们达到大小/ 2。
但是......没那么快，为什么第一种方法比“蛮力”方式更快？在第一种方法中，我们将中间指针递增大约/ 2倍。但是在蛮力的方式中，在我们的第二遍中，我们遍历列表，直到我们达到大小/第2个节点。那么这两种方法不一样吗？为什么第一个优于第二个？
//finding middle element of LinkedList in single pass
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;
while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}
if(length%2 == 1){
middle = middle.next();
}
如果我们将代码修改为：
while(current.next() != null){
current = current.next();
middle = middle.next();
if(current.next() != null){
current = current.next();
}
}
从那以后，现在的任务减少了 length 不必增加，我相信这将给出相同的结果。
在一天结束时，两个解决方案都是O（N），因此它是微优化。
如 @Oleg Mikheev 建议，为什么我们不能使用 Floyd的循环寻找算法 找到中间元素，如下：
private int findMiddleElement() {
if (head == null)
return -1; // return -1 for empty linked list
Node temp = head;
Node oneHop, twoHop;
oneHop = twoHop = temp;
while (twoHop != null && twoHop.next != null) {
oneHop = oneHop.next;
twoHop = twoHop.next.next;
}
return oneHop.data;
}
第一个答案有多个优点：
由于这两种方法具有相同的复杂度O（N），因此任何对效率的分析都需要谨慎，可能涉及具体的实施和成本模型。但是，对于最天真的实现，第一种方法可以保存一些循环变量增量。
它为你节省了一个变量的空间 - 两个指针v.s.长度，计数器和一个指针。如果它是一个巨大的列表，并且长度溢出怎么办？
但是，如果考虑一些特定的模型，那么第二种方法可能会好得多。如果元素在内存中都相邻，并且列表足够大，则缓存只能容纳一个连续内存的位置，第一种方法可能会产生一些内存访问成本。在一天结束时，这两种方法大多是等效的。当然，第一种方法中使用的技术更加华丽，思考过程在其他环境中可能会有用。
public void middle(){
node slow=start.next;
node fast=start.next;
while(fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
}
System.out.println(slow.data);
}
10-> 9-> 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1->
五
这是经典的求职面试问题。
他们不希望你带有算法O（n），因为它们都具有O（n）复杂度。普通人会说，如果我不经过一次就没有办法知道中间在哪里（所以一次寻找长度，并且第二次寻找中间是两次通过采访你的人）。他们希望你在盒子外面思考，并找出你提到的包括两个指针的方式。
所以复杂性是一样的，但思维方式不同，采访你的人希望看到这一点。