Как найти средний элемент связанного списка за один проход?

Один из самых популярных вопросов о структурах данных и алгоритме, который чаще всего задают при телефонном интервью.

Обманывая и делая два прохода одновременно, параллельно. Но я не знаю, понравится ли это рекрутерам.

Может быть сделано в одном связанном списке, с хорошим трюком. Два указателя перемещаются по списку, один с двойной скоростью. Когда быстрый достигает конца, другой - на полпути.

Если это не двусвязный список, вы можете просто посчитать и использовать список, но для этого потребуется удвоить объем памяти в худшем случае, и он просто не будет работать, если список слишком велик для хранения в памяти.

Простое, почти глупое решение - просто увеличивать средний узел каждые два узла.

function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}

Разрабатывая ответ Хендрика

Если это двусвязный список, выполните итерацию с обоих концов

function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

Данный [1, 2, 3] => 2

1, 3
1, 2
2, 2

Данный [1, 2] => 1

1, 2
1, 1

Данный [1] => 1

Данный [] => null

Создайте структуру с указателем, способным указывать на узлы связанного списка, и с целочисленной переменной, которая ведет счетчик количества узлов в списке.

struct LL{
    struct node *ptr;
    int         count;
}start;

$start.ptr$$start.count = 1$
$start.count$

$start.count$

Создайте динамический массив, где каждый элемент массива является указателем на каждый узел в списке в порядке обхода, начиная с начала. Создайте целое число, инициализированное 1, которое отслеживает количество посещенных вами узлов (которое увеличивается каждый раз, когда вы переходите на новый узел). Когда вы дойдете до конца, вы узнаете, насколько велик список, и у вас есть упорядоченный массив указателей на каждый узел. Наконец, разделите размер списка на 2 (и вычтите 1 для индексации на основе 0) и выберите указатель, содержащийся в этом индексе массива; если размер списка нечетный, вы можете выбрать, какой элемент вернуть (я все равно верну первый).

Вот некоторый Java-код, который помогает понять суть (даже если идея динамического массива будет несколько проблематичной). Я хотел бы предоставить C / C ++, но я очень ржавый в этой области.

public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}

Считается ли рекурсия более чем одним проходом?

Просматривать список до конца, передавая целое число по ссылке. Сделайте локальную копию этого значения на каждом уровне для дальнейшего использования и увеличивайте счетчик ссылок, поступая в следующий вызов.

На последнем узле разделите счет на два и truncate / floor () результат (если вы хотите, чтобы первый узел был «средним», когда имеется только два элемента) или округлите (если вы хотите, чтобы второй узел был середина"). Используйте индекс на основе нуля или единицы соответственно.

Разматывая, сопоставьте количество ссылок с локальной копией (которая является номером узла). Если равно, верните этот узел; иначе вернуть узел, возвращенный из рекурсивного вызова.
,

Есть и другие способы сделать это; некоторые из них могут быть менее громоздкими (я думал, что видел, как кто-то сказал, прочитал его в массив и использовал длину массива, чтобы определить среднюю оценку). Но, честно говоря, нет хороших ответов, потому что это глупый вопрос для интервью. Номер один, кто все еще использует связанные списки ( поддерживающее мнение ); Во-вторых, найти средний узел - это произвольное академическое упражнение, не имеющее ценности в реальных сценариях; В-третьих, если бы мне действительно нужно было знать средний узел, мой связанный список выставлял бы количество узлов. Это свойство легче поддерживать, чем тратить время на обход всего списка каждый раз, когда мне нужен средний узел. И, наконец, в-четвертых, каждому интервьюеру нравятся или отклоняются разные ответы - то, что один интервьюер считает хитрым, другой назовет смешным.

Я почти всегда отвечаю на вопросы интервью с большим количеством вопросов. Если я получу такой вопрос (у меня его никогда не было), я бы спросил: (1) Что вы храните в этом связанном списке, и существует ли более подходящая структура для эффективного доступа к среднему узлу, если действительно есть необходимость в этом? ; (2) Каковы мои ограничения? Я могу сделать это быстрее, если память не является проблемой (например, ответ массива), но если интервьюер думает, что накопление памяти расточительно, я потерял сознание. (3) На каком языке я буду развиваться? Почти у каждого современного языка, который я знаю, есть встроенные классы для работы со связанными списками, которые делают обход списка ненужным - зачем изобретать что-то, что было настроено для эффективности разработчиками языка?

Используя 2 указателя. Увеличивайте одно на каждой итерации, а другое - на каждой второй итерации. Когда первый указатель указывает на конец связанного списка, второй указатель указывает на средний режим связанного списка.