Given a singly linked list: 1->2->3->4->5, Change it to 1->5->2->4->3 using O(1) space?

Question

I am looking for sample code which can impress an interviewer.

Answer 1

If we know the total number of element in the list, then prepare two list half and half.

First Half :- 1->2->3
Second Half -> 4->5

Then Reverse the second which will be 5->4;

Then you can merge the list with first list pointer moving each time two times, and second pointer one time.
1->5>2->4->3;
O(1) space is nothing but constant space, so you are allocating just some pointers to reverse the linked list and one pointer to point the new list .