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

Напишите программу, которая переворачивает заданный двусвязный список.

См., например, диаграммы ниже.

          (a) Original Doubly Linked List  

          (b) Reversed Doubly Linked List  

Подход: в предыдущем посте двусвязный список реверсируется путем замены указателей prev и next для всех узлов, изменения prev заголовка (или начала), а затем изменения указателя заголовка в конце. В этом посте мы создаем функцию push, которая добавляет данный узел в начало заданного списка. Мы проходим по исходному списку и один за другим передаем текущий указатель узла в функцию push. Этот процесс перевернет список. Наконец, верните новую голову этого перевернутого списка.

Выход:

Original list: 10 8 4 2
Reversed list: 2 4 8 10

Временная сложность: O(n).