@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)?
Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(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; }

EDIT: this is in fact O(nlogn) time and O(logn) space, as discussed earlier in the thread.
O(n)O(nlogn) time and O(log n) space solution: Start at the beginning of the list with n (== size of list) to go.
 Each step store the current head and advance half the distance (n/2)
 Then print (recursively) that right half, and then the left half, effectively doing the reversal
 Handle odd ns by printing the midpoint element in between the left and right halves
No overlap between calls / prints, therefore O(n) timeas mentioned earlier in the thread, recursion is T(n) = n/2 + 2T(n/2) = O(nlogn) At the max depth you'll have logn recursive calls, therefore O(logn) space
public static void printImmutableListReverse(LLNode l) { if (l == null) return; if (l.next() == null) { System.out.println(l.elem() + " > "); return; } int n = 0; LLNode curr = l; while (curr != null) { n++; curr = curr.next(); } printImmutableListReverse(l, n); System.out.println(""); } private static void printImmutableListReverse(LLNode l, int n) { if (n == 0) { return; } if (n == 1) { System.out.print(l.elem() + " > "); } else { LLNode half = l; LLNode oddMid = null; for (int i = 0; i < n / 2; i++) { half = half.next(); } if (n % 2 == 1) { oddMid = half; half = half.next(); } printImmutableListReverse(half, n / 2); if (oddMid != null) { System.out.print(oddMid.elem() + " > "); } printImmutableListReverse(l, n / 2); } }

@ariel Max depth of recursion doesn't cut it. The entire recursive call stack counts towards that space,
which is aboutO(n)
. You are taking up linear amount of space.EDIT: Sorry, my bad. Look at comments below.

@babhishek21 I think you're incorrect. The max depth of the recursive call is exactly the size of the call stack, and therefore the space the algorithm takes up. At any given moment you will not have more than log(n) calls on the stack, each taking up constant space, therefore O(logn) space.

@babhishek21 Funny that you go against the correct O(log n) space claim but not against the wrong O(n) time claim :)
@ariel You put quite some effort into an approach already shown to be wrong in the first few posts of this thread...

@StefanPochmann Indeed, missed that (was heading on the problem and prematurely posting before exhausting the discussion). Edited original comment with correction.

@ariel Ah, right. Of course it's good to solve on your own first, and that's what takes the most effort. I didn't think that through, probably because I always read other people's solutions after writing my own and before potentially posting mine.
Still wishing this would become a real LeetCode problem, then I'd write up my own idea that I think is nice, but I guess that won't happen anymore now that LeetCode only does contest problems and because this problem is not suited well for contests...

@StefanPochmann Shoot. My bad. The space complexity is something I'm more interested with, since a O(n) or longer runtime is guaranteed (since it takes O(n) to just find out the length of the list). Did not think about looking that way.
@ariel You are right, the space requirement is indeed O(logn). My bad.

@StefanPochmann Ask @1337c0d3r to let you put this in. I'm sure this was asked in some interview by someone on Earth.

@StefanPochmann No, this is not true. We still want to add more interesting problems like this that are not suited well for contests.
Let's work together to publish this problem, shall we? :)

@1337c0d3r Oh, sorry, it's just that I think I haven't seen noncontest problems in a long time. I should work on other stuff, not leetcode, but I guess I can help a bit.