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





@1337c0d3r said in Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(n)):
@stevenxyx Does recursion count as space as well?
I'm not quite steven, but I'd say of course it does. In general, and here in particular. Otherwise the problem would be trivial and boring :stuck_out_tongue_winking_eye:

u can use stack data structure.
 while(head != null){
stack.push(head.val);
head = head.next;
}
while(stack.isEmpty() != true){
stack.pop();
}
Push will take o(n) and pop will also take o(n) so on average time complexity will be o(n) and as we are using stack space complexity will be o(n)
 while(head != null){


@StefanPochmann Less than O(n) space, I assume the target space complexity is O(log n) space?

I would try a Divide and conquer approach.
Break the list into two halves by advancing to the middle node, recursively print the second half in reverse, then recursively print the first half in reverse.
T(n) = 2 T(n/2) + n/2
Space should be O(log n).
EDIT: Oops, I missed the linear time complexity, this is not linear, it's O(n log n).

@1337c0d3r said in Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(n)):
@StefanPochmann Less than O(n) space, I assume the target space complexity is O(log n) space?
I don't know. I only have an O(sqrt(n)) space solution.

@1337c0d3r said in Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(n)):
T(n) = 2 T(n/2) + n/2
That's not linear, though.



@StefanPochmann I think that can find a solution with O(2*sqrt(n)) space complexity.It is a trivial. Find length in some way and split on chunks of(Sqrt(n) and save pointers to the beginning of each chunk in a memory. Then start from the last pointer and read sqrt(n) elements in a stack with capacity of sqrt(n) and print stack. I will do the same with next pointer till there are no more pointers left

@elmirap Yes, that's almost how I do it. I do have a neat little extra thing, though.
Just curious: Why do you say O(2*sqrt(n)) instead of O(sqrt(n))?

@StefanPochmann because I need to store sqrt(N) pointers ,one per each chunk in addition to sqrt(n) for the stack which is also roughly sqrt(n).Technically it is O (sqrt(n)), not O(2(sqrt(n)) but I wanted to emphasize that memory we need is 2*(sqrt*n)

@elmirap said in Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(n)):
Technically it is O(sqrt(n)), not O(2*sqrt(n))
You mean it's O(sqrt(n)) and O(2*sqrt(n)), right? Cause they're exactly the same. So it's not wrong to say O(2*sqrt(n)), just quite unusual, hence my curiosity.



