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

• for example :

Given the linked list : 4-5-12-1-3
Your program should print : 3-1-12-5-4

• I have updated the post

• This post is deleted!

• @stevenxyx Does recursion count as space as well?

• @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(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)

• @LMNTRIX The question already mentioned less than O(n) space.

• @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).

• @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.

• T(n) = 2 T(n/2) + n/2

That's not linear, though.

• Isn't the problem with space complexity O(sqrt(n)) valid solution?

• @elmirap Yes, my O(sqrt(n)) space solution is valid.

• @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)

• 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.

• @1337c0d3r yes, recursion indeed counts--more memory on the stack. :)

• On the chunk idea. The follow up to this question is (from interview) : what is the optimal chunks or partitions of the linked list (optimal in reducing memory)?

• @stevenxyx isn't sqrt(n). At least if i minimize x+ n/x , x = sqrt(n)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.