4
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • \$\begingroup\$ Is this a homework question? What if you could do the task better without using linked lists? \$\endgroup\$ Dec 15, 2018 at 14:29
  • \$\begingroup\$ @200_success No not a homework question..you can suggest without using linked list too. \$\endgroup\$
    – Hanoi
    Dec 15, 2018 at 14:49

3 Answers 3

4
\$\begingroup\$

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.

\$\endgroup\$
12
  • \$\begingroup\$ Do you think that std::stable_partition will be slower? Though your solution is definitely the easiest. \$\endgroup\$ Dec 15, 2018 at 15:49
  • \$\begingroup\$ In the general case I think two linear scans will be faster except when the input is already properly sorted. Of course I'd need to measure to be sure. The big time consumer would be branch mispredictions whenever determining if to print or not in the linear scans. But regardless it's not possible to do better than O(n). \$\endgroup\$
    – Emily L.
    Dec 15, 2018 at 15:54
  • 1
    \$\begingroup\$ @Hanoi Change "print" into append to output array :) \$\endgroup\$
    – Emily L.
    Dec 15, 2018 at 16:41
  • 1
    \$\begingroup\$ @Hanoi make a linked list of the input, iterate over it once, copy even numbers into a new linked list, iterate over the lined list once more and copy the odd numbers into the output linkde list, print. The solution doesn't change depending on which implementation of list you use in this case :) \$\endgroup\$
    – Emily L.
    Dec 15, 2018 at 16:52
  • 2
    \$\begingroup\$ @Hanoi the question as formulated is basically "I have this easy problem I want to solve but you must do it in the most convoluted manner possible and it won't matter for the result" :) \$\endgroup\$
    – Emily L.
    Dec 15, 2018 at 17:06
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Solution with linked lists: sed -i 's/vector/list/g' solution.cpp :D \$\endgroup\$
    – Emily L.
    Dec 15, 2018 at 18:06
  • \$\begingroup\$ @EmilyL., ikr, I would choose that solution any day of the week over reimplementing linked list \$\endgroup\$ Dec 15, 2018 at 18:24
4
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.