Поиск k-го последнего элемента односвязного списка: объяснение ответа

#algorithm #linked-list #singly-linked-list

#алгоритм #связанный список #односвязный список

Вопрос:

Когда вам нужно найти k -й последний элемент односвязного списка, обычный наивный подход заключается в выполнении двух проходов. Первый, чтобы найти длину списка, а второй, чтобы выполнить итерацию до (length-k)th элемента.

В то время как оптимизированная версия использует два указателя:

p1 ссылка на начало списка
p2 быть k -м элементом впереди p1

Это позволяет нам возвращать p1 элемент s, когда p2 он достигает конца списка. Я не понимаю, почему второй подход быстрее первого, когда в обоих случаях у нас есть один указатель, повторяющийся по всему списку, а другой до (length-k)th элемента.

Связано ли это с оптимизацией кэша?

Спасибо.

1. когда длина = k, то в 1-м подходе вы повторяете 2 * k раз, но во 2-м подходе вы повторяете только k раз

2. Оба алгоритма имеют одинаковую сложность. Какой из них быстрее на практике, зависит от фактической реализации.

3. Это помогло бы написать код для обоих подходов. Тогда разница была бы более очевидной.

Ответ №1:

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

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

Когда вы просматриваете список, допустим, вы запоминаете указатель в каждой (k / m)-й позиции для некоторых m. Вам нужно запомнить только последние m 1 из этих указателей. Затем, когда вы дойдете до конца списка, вместо повторения с начала, начните с самого старого указателя, который вы запомнили. Он будет находиться между k и k (k / m) элементами за концом, поэтому вам нужно только переместить его вперед не более чем на k / m позиций.

Ответ №2:

Рассмотрим неравномерное время доступа к памяти и односвязный список длиной n:
— при подходе с подсчетом итераций доступ к одному и тому же узлу будет разделен на n обращений
— при подходе с запаздывающим указателем доступ к одному и тому же узлу будет разделен на k обращений
с помощью кэша LRU (/ с каждым уровнем кэша LRU), первый с большей вероятностью вызовет нехватку емкости, чем второй.