Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
I think you are right.
For your question : "space; O(1) - I don't think making a list into two halves is an extra space. So, it takes constant space... I'm not 100 % sure about this. Can any one confirm."
my answer is that when you are traversing to middle of the list you are just forwarding the pointer towards middle node, which is O(1) space operation.
Hence it is surely O(1) space solution.
but how would you know which node is middle node. unless you traverse till the end you will not know the middle element. so we need to traverse again then it would be O(n2).
Please clarify.
There are many ways to do it.. One simple technique is
- arsragavan March 05, 20141) Traverse to the middle node
2) Seperate the list starting from the next node of middle node.
So now you will have two list...
List1 - header to middle node
List2 - next of middle node to tail
3) Do a two- way merge on List1 and List2
complexity: O(n), n is the total no of nodes in the list,
space; O(1) - I don't think making a list into two halves is an extra space. So, it takes constant space... I'm not 100 % sure about this. Can any one confirm..