Учитывая один связанный список с нечетным числом узлов, каковы 2 способа найти средний узел путем обхода списка только один раз?

Question

Учитывая один связанный список с нечетным числом узлов, каковы 2 способа найти средний узел путем обхода списка только один раз?

Об этом спрашивали в интервью IBM ISL.

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

У меня есть один связанный список, скажем, число узлов нечетное. Подскажите 2 способа нахождения среднего узла путем обхода списка только один раз?

Я ответил, взять 2 указателя p1 & p2 перемещает p2 на 2 узла и p1 на 1 узел. Когда p2 равно нулю, p1 находится в среднем узле.

Интервьюер ответил: это самый простой способ, используя 2 указателя. Скажи мне еще один способ. Подсказка: есть ли свойство компилятора, которое можно использовать?

Может кто-нибудь дать мне способ использовать подсказку?

0

c++linked-list list

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

#include <vector>
#include <list>

typedef std::list<int> listT;

listT::const_iterator
find_middle(const listT &list)
{
std::vector<listT::const_iterator> v;
for (listT::const_iterator i = list.begin() ; i != list.end() ; ++i)
v.push_back(i);

return v[v.size() / 2];
}

5