Firstly we place a pointer at middle element of the link list.This can be done in n/2 or O(n) by
initially keeping two pointers pointing to start node.Incrementing one ptr by 1(let say p=p->next) and other by 2(let say q=q->next->next) till (q!=null && q->next!=null&& q->next->next!=null).When this loop terminates ptr p will be at middle of link list(LL).
This middle node will be even numbered node if there are even no. of node in LL.Now we need to increment p by 1 and need a new ptr (let say odd) which points to starting node.After this we just need to swap the data (of node to which ptrs are pointing ) and increment both ptrs( odd and p) by 2 .
If no. of nodes in LL are odd then the (extra)increment of p by 1 which was done previously is not needed .
finding if LL contains even or node no. of nodes can be done in the same loop which is used to find middle ele of LL .So no extra time required.
pls correct me if I am wrong.