Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(n))

I think we can use "reversebinary search" method. We using a Stack<Node> indexs to store the Nodes that at at positions 1, 2, 4, 8, 16, 32 ...., and using another stack to reversely print each region.
 1  2 3  4 5 6 7  8 9 10 11 12 13 14 15  16 17 18 19 20 21 22 23 24 25
Thus, the time complexity is O(n), and spaces complexity is maximum at (n/2 + log(n/2)), where (n/2) is used to print the last region, and log(n/2) is used to store the indexes.
We can also using reverse binary search to print the last region if we want to save more space.

@gschengcong (n/2 + log(n/2)) doesn't fulfill the "less than linear space" requirement, though. So you'd really have to do the extension you mention in the last sentence. What's the space complexity then? Is it O(log^{2} n)?

@StefanPochmann I think your idea roots from the socalled "Skip List" https://en.wikipedia.org/wiki/Skip_list

My solution, I think space is log(N):
def reverse_print(start, end): if start == end: return slow = fast = start while fast.next != end and fast.next.next != end: slow = slow.next fast = fast.next.next reverse_print(slow.next, end) print slow.val, reverse_print(start, slow) reverse_print(root, None)


@StefanPochmann Yes, time complexity should be NlogN.
Is there a better way with linear time and constant space?

@vincewu
My Given solution should do it O(n) with O(1) space .
Here is Code which written in Go. Logic it iterate list and reverse its pair nodes. i.e 123 4
iter 0: 2134 , iter1 : 3214, iter3: 4321reverseList(L *list) {
dummy = new(list)
dummy.next = L
cur := L
for( cur != nil && cur.next != nil ) {
tmp := cur.next
next := tmp.next
tmp.next = dummy.next
cur.next = next
dummy.next = tmp
}
cur := dummy.next
for (cur !nil) {
fmt.Println(cur.val)
}

O(sqrt(n)) space complexity and O(n) time complexity solution:
It is inspired by the fact that sqrt(n) * sqrt(n) = n and the "reverse words in a sentence" problemvoid reverse(ListNode* begin) { int n = 0; auto ptr = begin; while (ptr) { ++n; ptr = ptr > next; } int k = ceil(sqrt(n)); vector<ListNode*> tmp1(k, NULL), tmp2(k, NULL); int i = 0; ptr = begin; while (ptr) { tmp1[i] = ptr; ++i; for (int j = 0; j < k && ptr; ++j, ptr = ptr > next) ; } i = tmp1.size()  1; while (i >= 0 && tmp1[i] == NULL) i; if (i < 0) return; while (i >= 0) { auto p = tmp1[i]; for (int j = 0; j < k && p; ++j, p = p > next) tmp2[j] = p; for (int j = k  1; j >= 0; j) { if (tmp2[j]) { cout << tmp2[j] > val << " "; } } for (int j = 0; j < k; ++j) { tmp2[j] = NULL; } i; } cout << endl; }