假设您想以尽可能高效的方式找到链表的中间节点。给出的最典型的“最佳”答案是保持 2 个指针,一个中间指针和当前指针。并且当遇到的元素数可被 2 整除时递增中间指针。因此,我们可以在 1 次遍历中找到中间指针。高效,对吧?比蛮力更好,它涉及 1 次传球到最后,然后再传 1 次直到我们达到 size/2。
但是......不是那么快,为什么第一种方法比“蛮力”方式更快?在第一种方法中,我们将中间指针增加大约 size/2 倍。但是以蛮力的方式,在我们的第二遍中,我们遍历列表直到我们到达 size/2th 节点。那么这两种方法不一样吗?为什么第一个比第二个好?
//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();
}