Возможно ли иметь рекурсивную функцию с постоянным пространством?

Question

Я пытаюсь решить эту проблему: https://leetcode.com/problems/sort-list/ и ограничения: Time = O (nlog (n)) и Space = O (1).

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Из-за сложности времени это можно сделать, но из-за постоянного пространства я боролся, и многие люди публиковали решения, использующие сортировку слиянием с рекурсивной функцией, которая, как я не уверен, занимает только пространство O (1).

Что мне здесь не хватает? Можно ли реализовать рекурсивную функцию для односвязного списка с пробелом O (1)?

Answer 1

Вы ничего не пропустили. Рекурсивная сортировка слиянием занимает O(log(n)) пробел. Тем не менее, проверка leetcode на эффективность использования пространства не в состоянии определить разницу между O(1) и O(log(n)) - все, что они делают, это ограничивают память, запускают ее и видят, что она не взорвалась.

Если данные были в массиве, существует несколько эффективных решений, которые занимают O(1) дополнительного пространства. Самым простым из них является heapsort.

Тем не менее, с помощью односвязного списка, я сомневаюсь, что есть ответ, который на самом деле O(1) пробел.

ОБНОВЛЕНИЕ

Несмотря на то, что я сомневаюсь, это возможно. См. Комментарий Джима Мишеля.