Even-After-Odd (linked list)

#1

Will there only be 1s and 2s in the linked list provided or they can be any odd and even numbers. If so do I have to
sort the odd and even parts respectively?

#2

there can be any odd and even numbers

first all odd no should come and after that even number

for input
1 2 3 4 5 6
output should be
1 3 5 2 4 6

hence sorting will not work here

#3

What should be the right approach to solve this problem. What I am doing is traversing the list and deleting the odd elements and inserting them at the head.

#4

you can do that
but it not good to completely alter the list
you just have to rearrange the links of node

The idea is to split the linked list into two: one containing all even nodes and other containing all odd nodes. And finally, attach the odd node linked list after the even node linked list.
To split the Linked List, traverse the original Linked List and move all odd nodes to a separate Linked List of all odd nodes. At the end of loop, the original list will have all the even nodes and the odd node list will have all the odd nodes. To keep the ordering of all nodes same, we must insert all the odd nodes at the end of the odd node list. And to do that in constant time, we must keep track of last pointer in the odd node list.

#5

ohk. so the two lists need not be sorted right??

#6

Yes no need to sort them