algorithm - Reordering a linked list efficiently -

i got question in interview follows:

if have linked list this,

1->2->3->4->5->6

i have convert to,

1->6->2->5->3->4

and if is, this,

1->2->3->4->5->6->7

i have convert to

1->7->2->6->3->5->4

and, importantly, have modify original linked list , cannot make new linked list. thought of recursion this. but, couldn't solve it. moreover, constraint function can have head of linked list.

this can done in linear time o(n) , during interviews (unfortunately) counts more robustness of solution.

you can splitting original list 2 (as) equally sized (as possible) list, reversing second 1 , merging both of them element element (first element first list, second element second list etc). don't need additional space can use existing pointers.

for example:

1->2->3->4->5->6  1->2->3 , 4->5->6 // after split, 3 points null, 4 head of second list 1->2->3 , 4<-5<-6 // after reorder 1->6->2->3 , 4<-5 // first phase of merge 1->6->2->5->3 , 4 // second phase of merge 1->6->2->5->3->4    // last phase of merge 

you can find split point using running pointer. traverse list 1 pointer going 1 node @ time , 1 going 2 nodes @ time. when faster pointer hits end (null) slower pointer before split, node before split has point null instead of next node (in our case instead of 4) , next node (4) becomes head of second list.

reversing second list , merging simple pointer swapping.

just watch out null pointers :-)