Logic to solve the question

#1

Pls can I get some hint to solve the question.

#2

Do you want the general logic or how to do it specifically with a linked list?

#3

first pls give me the general logic.If I am unable to solve even after getting it then pls give the specific logic as I want to try the qstn b4 seeing the soln.

1 Like
#4

Okay, well if it was not a linked list then you could’ve simply sorted the array. But the comparator would’ve been

bool cmp (int a, int b) {
     return (a % 2) > (b % 2);
}

But this is a linked list so you can’t do this.

The other faster (and easier) way, but with extra memory is to store the odd numbers and even numbers in different arrays and then first print the odds followed by evens.

This can also be extended to linked lists.

#5

why is the logic of the comparator function so?

#6

If the number is odd (that is (a % 2) is 1), then it should be listed before b, if b is even (b % 2 is 0).

You can do it manually but this was cleaner according to me.

The other way is,

bool cmp (int a, int b) {
       // if the first number is even and the second number is odd, then swap
       if (a % 2 == 0 && b % 2 == 1) return true;
       // don't swap in other cases
       return false;
}
#7
#8

Pls help me to optimise this code to avoid tle.I have splitted the given LL into 2 LL one containing all odds and the other containing all evens and thn merged them.

#9

You are creating the linked list in O(n^2), which is not optimal.

#10

how to create the LL in more optimised way pls help me?

#11

As you are always inserting at the tail, just store the pointer of tail somewhere. So that you can just add one after that, rather than finding the tail again and again.

#12

ok i will try it.