Предположим, вы хотите найти средний node связанного списка как можно эффективнее. Самый типичный "лучший" ответ - поддерживать 2 указателя, средний и текущий. И чтобы увеличить средний указатель, когда количество встречающихся элементов делится на 2. Следовательно, мы можем найти середину за 1 проход. Эффективный, не так ли? Лучше, чем грубая сила, которая включает в себя 1 проход до конца, затем еще 1 проход, пока мы не достигнем размера /2.
НО... не так быстро, почему первый метод быстрее, чем метод "грубой силы"? В первом методе мы увеличиваем средний указатель примерно на размер /2 раза. Но в режиме грубой силы, на нашем втором пропуске, мы переходим к списку, пока не достигнем размера/2-го node. Разве эти два метода не одинаковы? Почему первое лучше второго?
//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 →
5
Это классический вопрос о собеседовании.
Они не хотят, чтобы вы пришли с алгоритмом O (n), потому что оба они имеют сложность O (n). Обычный человек скажет, что нет способа узнать, где находится середина, если я не пройду один раз (так что один раз, чтобы найти длину, и пройдя второй раз, чтобы найти середину, это два прохода для тех, кто вас соберет). Они хотят, чтобы вы думали вне поля, и выясните, как вы упомянули, включая два указателя.
Таким образом, сложность такая же, но способ мышления различен, и люди, которые берут интервью у вас, хотят это увидеть.