Программа Python для указания на следующий узел с более высоким значением в связанном списке с произвольным указателем

Дан односвязный список, в котором каждый узел имеет дополнительный «произвольный» указатель, который в настоящее время указывает на NULL. Нужно сделать так, чтобы «произвольный» указатель указывал на следующий узел с более высоким значением.

Мы настоятельно рекомендуем свернуть ваш браузер и сначала попробовать сами

Простое решение состоит в том, чтобы пройти все узлы один за другим, для каждого узла найти узел, который имеет следующее большее значение текущего узла, и изменить следующий указатель. Временная сложность этого решения составляет O(n ² ).

Эффективное решение работает за время O(nLogn). Идея состоит в том, чтобы использовать сортировку слиянием для связанного списка.
1) Перейдите по списку ввода и скопируйте следующий указатель в указатель арбитража для каждого узла.
2) Выполните сортировку слиянием для связанного списка, сформированного указателями арбитража.

Ниже приведена реализация вышеизложенной идеи. Все функции сортировки слиянием взяты отсюда. Взятые функции изменены здесь так, чтобы они работали с указателями арбитража, а не с указателями next.

Выход:

Result Linked List is:
Traversal using Next Pointer
5, 10, 2, 3,
Traversal using Arbit Pointer
2, 3, 5, 10,

Пожалуйста, обратитесь к полной статье о Указатель на следующий узел с более высоким значением в связанном списке с произвольным указателем для получения более подробной информации!