Programming Interview 38: Interweave a linked List with constant space and linear time

Step by step to crack Programming Interview questions Q38: Interweave a linked List with constant space and linear time
i.e. 1,2,3,4,5; After interweaving: 1,5,2,4,3

Solution:
1. Find the mid point of List and divide into 2 halves
1.1. e.g. 1,2,3,4,5, we have 1,2,3 and 4,5

2. Reverse the 2nd half
2.1. e.g. 4,5, we will have 5,4

3. Merge the two halves
3.1. e.g. Merge 1,2,3 and 5,4 will result in 1,5,2,4,3

[andreigiurgiu]

I would make mid->next=Reverse(mid->next); and then, for the interweaving, keep switching values between first half and second half, increasing first every iteration and second every 2 iterations; this would solve it in constant space.

[sumanthyss]

was struggling for the idea. One of the newer interview questions. Thanks!

[titombo]

Nice video! Congratulations! :)

First time I saw the title I didn't catch the idea, but looking to the example I guess it should Interweave in a specific way: The first points to the last, the 2nd to 2nd last, and so forth.

[nilaysaha]

not needed to do like that. there is a much easier way. 

A -> B -> C -> D -> E

 1> find first and last node. A, E. Strip those two from the list. New list: B ->C->D 
repeat step 1 with new list. you will get B, D.
remaining element C.

Thus we have the interweaved elements: A, E, B, D, C
simple is it not...?

[qtmomo]

Constant space means you have to solve this problem without a ton of new data?
that means you have to work with that list without creating a new one?
linear time is like passing through the list only once right?

[andreigiurgiu]

What about the constant space requirement? That's the trickiest thing about this problem...this way, your solution is incorrect.