can you please find the error. run time error for test case 1 and 4
link to my code - https://ide.codingblocks.com/s/239534
Run time error!
your code will give error when the last node is even, let me walk you through why
consider very simple case 1 1 2 or 1 2 2 whatever you like
so for the first call, head is at 1, it reaches
node* temp = even_odd(head->next);
now again it is called for 1
node* temp = even_odd(head->next);
again it called for 2
now, 2’s next is NULL
so in this call it returns head from the base case and returns NULL to temp
in the previous call now temp is NULL
it enters the if since head%2 == 0 (for 2)
inside a is assigned to temp and then a->next is accessed
but since temp is NULL, a is NULL
so a->next is a NULL pointer exception
Now, the fix for this is simple
if(head==NULL || head->next == NULL) return head;
use this
now, u will still notice that this gives wrong answer on test case zero
let me walk you through that as well
what this question demand is for u to do the ordering in place as in
the even number that appears before another even number initially should come before in the result as well
for eg
in 1 2 3 4
answer should be
1 3 2 4
even though
3 1 4 2
3 1 2 4 are also correct logically but not in accordance to the question
this is where your code fails
it changes the ordering of the numbers
by putting the farthest number before since it goes in reverse order from recursive calls
alternate approaches:
Algorithm:
…1) Get pointer to the last node.
…2) Move all the even nodes to the end.
………a) Consider all even nodes before the first odd node and move them to end.
………b) Change the head pointer to point to the first odd node.
………b) Consider all even nodes after the first odd node and move them to the end.
Method 2
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.
take four pointers and initialise all to NULL
oddend and evenend to store the ends of even number and odd numbers
and oddstart and evenstart to store the beginning of them
check the first node if it is odd or even and point oddstart or evenstart accordingly
now for temp = head->next start running a loop
in the loop:
if an odd number is encountered and if oddstart is NULL point oddstart to it else if oddstart->next==NULL point odd end else point oddend->next to this temp and move oddend to it next
similarly follow the simlar steps for even numbers
at the end of the loop point oddend to even start and return oddstart as your new head