Stable-sorting all even numbers before odd numbers in a linked list Given a Linked List of integers, write a function to modify the linked
  list such that all even numbers appear before all the odd numbers in
  the modified linked list. Also, keep the order of even and odd
  numbers same. - (from geeksforgeeks: Segregate even and odd nodes in a Linked List)
  
  Example:
  
  Input:

3
7
17 15 8 9 2 4 6
4
1 3 5 7
7
8 12 10 5 4 1 6

  
  Output:

8 2 4 6 17 15 9
1 3 5 7
8 12 10 4 6 5 1



My Approach: get pointer to the last node of list. And then traverse the list starting from the head node and move the odd valued nodes from their current position to end of the list.Also if all the node's data is even or odd then list remains unmodified so first I check if this is the case then I simply return(len is total number of nodes &amp; count is total number of even data nodes).

I am getting right answer on an IDE, but on other IDE where the code needs to be submitted, it's showing time limit exceeded.

How do I optimize my code?

#include &lt;iostream&gt;
using namespace std;
int flag=0;
struct Node{
    int data;
    Node* next;
};
void addkey(struct Node** head_ref,int key)
{struct Node* temp=(struct Node*)malloc(sizeof(Node));
temp-&gt;next=NULL;
temp-&gt;data=key;
    if(*head_ref==NULL)
    {
      *head_ref=temp;  
    }
    else
    {
        struct Node* ptr=*head_ref;
        while(ptr-&gt;next!=NULL)
        {
            ptr=ptr-&gt;next;
        }
        ptr-&gt;next=temp;
    }
}
void segregate(struct Node**head_ref)
{   int len=0,count=0;
    struct Node* ptr1=*head_ref;
    struct Node* ptr2=*head_ref;
    struct Node* prev=NULL;
    while(ptr2-&gt;next!=NULL)
    {
        if((ptr2-&gt;data)%2==0) count++;  
        ptr2=ptr2-&gt;next;
        len++;
    }
    if(ptr2-&gt;data%2==0)  count++;
    if(count==len+1||count==0)  return;
    struct Node* ptr5=ptr2;
    while(ptr1!=ptr5-&gt;next)
    {
        if((ptr1-&gt;data%2)==0)
        { if(flag==0) {
        *head_ref=ptr1;
        flag=1;}
            prev=ptr1;
            ptr1=ptr1-&gt;next;
        }
        else
        {
          if(prev!=NULL)  prev-&gt;next=ptr1-&gt;next;
            ptr2-&gt;next=ptr1;
            ptr2=ptr2-&gt;next;
            ptr1=ptr1-&gt;next;
            ptr2-&gt;next=NULL;
        }
    }
}
void printlist(struct Node* head)
{
    if(head==NULL) return;
    else
    {
        while(head!=NULL)
        {
            cout&lt;&lt;head-&gt;data&lt;&lt;" ";
            head=head-&gt;next;
        }
    }
}
int main() {
    int T ;
    cin&gt;&gt;T;
    while(T--)
    {
        int n;
        cin&gt;&gt;n;
        struct Node* head=(struct Node*)malloc(sizeof(Node));
        head=NULL;
        for(int i=0;i&lt;n;i++)
        {int key;
         cin&gt;&gt;key;
         addkey(&amp;head,key);
        }
        segregate(&amp;head);
        printlist(head);cout&lt;&lt;"\n";
    }
    return 0;
}
The best way to accelerate your code is to defenestrate it (9.82 m/s2) and use the correct algorithm.

You don't need to do anything fancy. Just go through the list once, print all the even numbers, go through once more and print the odd ones.