Сортировка связанного списка после преобразования элементов в их квадраты

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

Примеры :

Input:  1->2->3->4->5
Output: 1->4->9->16->25

Input: (-2) -> (-1) -> 0 -> 1 -> 2
Output: 0 ->1 -> 1 -> 4 -> 4

Для массивов: проблема сделать то же самое для массивов обсуждается в этой статье — Сортировка массива после преобразования элементов в их квадраты.

Подход : Задача может быть решена путем разделения данного списка на два разных связанных списка из точки перехода (отрицательного к положительному), один из которых содержит только отрицательные элементы, скажем « l1 », а другой содержит положительные элементы, скажем, « l2 ». Возведите в квадрат все элементы списка l1 и переверните его, а также возведите в квадрат все элементы списка l2, теперь объедините два отсортированных списка, чтобы получить результирующий список.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N), N — количество узлов
Вспомогательное пространство : O(1)