Задачи с собеседований: найти середину связного списка

Задача обычно формулируется так: имеется указатель на начало списка и необходимо найти середину связного списка (в общем случае – произвольный элемент номер n).

В информатике, связный список — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Достоинства связных списков:

• эффективное (за константное время) добавление и удаление элементов
• размер ограничен только объёмом памяти компьютера и разрядностью указателей
• динамическое добавление и удаление элементов

Недостатки

Недостатки связных списков вытекают из их главного свойства — последовательного доступа к данным:

• сложность прямого доступа к элементу, а именно определения физического адреса по его индексу (порядковому номеру) в списке
• на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
• некоторые операции со списками медленнее, чем с массивами, так как к произвольному элементу списка можно обратиться, только пройдя все предшествующие ему элементы
• соседние элементы списка могут быть распределены в памяти нелокально, что снизит эффективность кэширования данных в процессоре
• над связными списками, по сравнению с массивами, гораздо труднее (хоть и возможно) производить параллельные векторные операции, такие, как вычисление суммы: накладные расходы на перебор элементов снижают эффективность распараллеливания

Простое решение

Приступая к задаче вы, вероятно, начнете с простого решения, в котором вы пройдете по всему связанному списку до конца, чтобы найти конец, а вторым проходом найти требуемую середину.

После этого ответа интервьюер наверняка попросит вас найти средний элемент за один проход.

Найти середину связного списка: сложное решение

Понадобятся два указателя: P1 и P2. В итерации сдвигаем указатель P1 на два элемента, а P2 на один. К моменту когда P1 достигнет конца списка (только нужно проверять, чтобы он не вышел за пределы, но это зависит от реализации), P2 будет указывать на середину.

Еще решение

Нужно взять два указателя на голову списка, первым отсчитать n элементов с начала списка, далее взять второй указатель на голову списка и двигать далее их уже одновременно, пока первый не достигнет конца. Тогда второй указатель будет указывать на n-й элемент с конца.