Обратный связанный список размером с 7 миллионов узлов эффективно использует потоки

Question

Мне задали этот вопрос, чтобы отменить один и тот же список с размером 7 миллионов узлов, эффективно используя потоки. Использование рекурсии не представляется выполнимым, если существует так много узлов, поэтому я выбрал divide и conquer, где в каждом потоке задан кусок связанного списка, который обращается вспять, просто делая указатель узла обратно на предыдущий узел, сохраняя ссылку на текущий, будущий и прошлый узел, а затем добавляя его с обратными кусками из других потоков. Но интервьюер настаивал на том, что размер списка ссылок неизвестен, и вы можете сделать это, не найдя размер в эффективном режиме. Ну, я не мог понять, как бы ты это сделал?

Answer 1

Такие вопросы я хотел бы реализовать «сверху-вниз»:

1. Предположим, что у вас уже есть класс, которые реализуют Runnable или расширяет тему, из которых можно создавать экземпляры и запускать каждый экземпляр получает два параметра : указатель на узел в списке и количество узлов для обратного
2. Ваш main проходит через все 7 миллионов узлов и «отметит» отправные точки для ваших потоков, скажем, у нас есть 7 потоков, отмеченные точки будут: 1, 1,000,000, 2,000,000, ... сохранить отмеченные узлы в массиве или любую структуру данных, которая вам нравится
3. После того, как вы закончили «отметку начальных точек, создайте потоки и дайте каждой из них свою начальную точку и счетчик. 1 000 000
4. После того, как все потоки выполнены,« склейте »каждую из точек маркировки, чтобы вернуться к последнему узла предыдущего потока (который должен быть сохранен в другой «статической» упорядоченной структуре данных).

Теперь, когда у нас есть план, все, что осталось сделать, это реализовать (значительно простой) алгоритм, который даст число N и узел x, он изменит следующие N узлов (включая x) в отдельно связанный список: