​​Как найти средний элемент в LinkedList за один проход? Это | Тостер

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

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

Все программисты знают, что средний элемент в LinkedList несложно найти, определив длину списка, последовательно пройдя все его узлы, пока не дойдёшь до NULL в первом проходе. А затем, пройдя половину из них во втором проходе. Когда же их просят решить эту задачу за один проход, многие теряются.

Решение:
В этой задаче достаточно ввести два указателя. Первый будет увеличиваться при прохождении одного узла списка, второй – при прохождении двух узлов. В момент, когда второй указатель дойдёт до конца списка (наткнётся на NULL), первый будет указывать на середину списка.

Тостер