Stable-sorting all even numbers before odd numbers in a linked list

Question

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 & 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 <iostream>
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->next=NULL;
temp->data=key;
    if(*head_ref==NULL)
    {
      *head_ref=temp;  
    }
    else
    {
        struct Node* ptr=*head_ref;
        while(ptr->next!=NULL)
        {
            ptr=ptr->next;
        }
        ptr->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->next!=NULL)
    {
        if((ptr2->data)%2==0) count++;  
        ptr2=ptr2->next;
        len++;
    }
    if(ptr2->data%2==0)  count++;
    if(count==len+1||count==0)  return;
    struct Node* ptr5=ptr2;
    while(ptr1!=ptr5->next)
    {
        if((ptr1->data%2)==0)
        { if(flag==0) {
        *head_ref=ptr1;
        flag=1;}
            prev=ptr1;
            ptr1=ptr1->next;
        }
        else
        {
          if(prev!=NULL)  prev->next=ptr1->next;
            ptr2->next=ptr1;
            ptr2=ptr2->next;
            ptr1=ptr1->next;
            ptr2->next=NULL;
        }
    }
}
void printlist(struct Node* head)
{
    if(head==NULL) return;
    else
    {
        while(head!=NULL)
        {
            cout<<head->data<<" ";
            head=head->next;
        }
    }
}
int main() {
    int T ;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        struct Node* head=(struct Node*)malloc(sizeof(Node));
        head=NULL;
        for(int i=0;i<n;i++)
        {int key;
         cin>>key;
         addkey(&head,key);
        }
        segregate(&head);
        printlist(head);cout<<"\n";
    }
    return 0;
}

Answer 1

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.

Answer 2

Code Review (or its absence)

There are way too many problems to talk about. This is definitely not idiomatic C++14, let alone C++98. Please grab a book from this list. The algorithm you are searching for though is called "stable partition".

Better solution

Emily's answer is already great. Use it if you need to just solve the problem.

Alternative solution

Here is the C++14 solution with standard library:

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using in_iterator = std::istream_iterator<int>;
using out_iterator = std::ostream_iterator<int>;

void iteration(int count) {
    std::vector<int> values(count);
    std::copy_n(in_iterator{std::cin}, count, 
                values.begin());

    std::stable_partition(values.begin(), values.end(), 
                          [](auto x) {return x % 2 == 0;});

    std::copy(values.begin(), values.end(), 
              out_iterator{std::cout, " "});
}

int main() {   
    int test_count = 0;
    std::cin >> test_count;
    for (; test_count >= 0; --test_count) {
        int value_count = 0;
        std::cin >> value_count;
        iteration(value_count);
        std::cout << '\n';
    }
}

I believe everything happening in main() is fairly obvious.

std::vector<int> values(count);
std::copy_n(in_iterator{std::cin}, count, 
            values.begin());

Those two lines initialize the values vector, by first creating the vector to hold count elements, then copying count elements from std::cin into values.

The next statement is just invocation of the algorithm from standard library.

The last line of the iteration function just copies the whole of the values into the std::cout stream.

Solution with linked list will be the same, just way more lengthier. One can also reimplement the stable partition too, if you feel like it.

Answer 3

Bug: Infinite loop

If your program runs on a list that ends in an odd number, it will run forever in an infinite loop. For example, try this input:

1
3
1 2 3

The problem is with the termination condition of your loop:

while(ptr1!=ptr5->next)

ptr5 is the last element of the original linked list (e.g. node 3), and you are trying to terminate your loop when you have iterated through each element (get past node 3). However, if the last element is an odd number, it will be moved to the end of the list, and ptr1 will never actually "get past ptr5". Instead, it will only catch up to it, move it, and then keep iterating through the odd numbers of the list over and over.

I made some minor edits to your program to fix the problem, although your algorithm is still overly complicated and you should think about simpler ways of solving the same problem:

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->next!=NULL)
    {
        if((ptr2->data)%2==0) count++;
        ptr2=ptr2->next;
        len++;
    }
    if(ptr2->data%2==0)  count++;
    if(count==len+1||count==0)  return;
    struct Node* ptr5=ptr2;
    while(ptr1!=ptr5->next)
    {
        if((ptr1->data%2)==0)
        { if(flag==0) {
        *head_ref=ptr1;
        flag=1;}
            prev=ptr1;
            // I added this termination condition
            if (ptr1 == ptr5)
                break;
            ptr1=ptr1->next;
        }
        else
        {
          if(prev!=NULL)  prev->next=ptr1->next;
            ptr2->next=ptr1;
            ptr2=ptr2->next;
            // I added this termination condition
            if (ptr1 == ptr5) {
                ptr2->next=NULL;
                break;
            }
            ptr1=ptr1->next;
            ptr2->next=NULL;
        }
    }
}

Example of a simpler solution

This solution assumes that you actually need to create a new sorted list instead of just printing out the answer. It iterates through the original list and places each element into one of two lists. Then it joins the two lists and returns the joined list.

void segregate(struct Node**head_ref)
{
    struct Node *evenList = NULL;
    struct Node *evenTail = NULL;
    struct Node *oddList  = NULL;
    struct Node *oddTail  = NULL;

    // Separate nodes into two lists.
    for (struct Node *p = *head_ref; p != NULL; p = p->next) {
        if ((p->data) % 2 == 0) {
            if (evenTail != NULL)
                evenTail->next = p;
            else
                evenList = p;
            evenTail = p;
        } else {
            if (oddTail != NULL)
                oddTail->next = p;
            else
                oddList = p;
            oddTail = p;
        }
    }

    // Terminate odd list with NULL.
    if (oddList != NULL)
        oddTail->next = NULL;
    // Place odd list at the end of the even list.
    if (evenList != NULL)
        evenTail->next = oddList;
    else
        evenList = oddList;

    *head_ref = evenList;
}