Tuesday, 21 February 2017

C Program to Segregate Even and Odd Nodes in a Linked List

This Question has appeared in the interview of Amazon

Question was like this 

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.

Input

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,N is the number of elements in Linked List.
The second line of each test case contains N input,elements in Linked List.


Output 

Print the all even numbers then odd numbers in the modified Linked List.

Constraints 

1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ size of elements ≤ 1000
 


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


C Program is given below to segregate the nodes in the same manner given above

 Algorithm:
…1) First Set the pointer to the last node.
…2) Then move all the odd nodes to the end of Linked List
……..a) Consider all odd nodes before the first even node and move them to end.
……..b) Change the head pointer to point to the first even node.
……..b) Consider all odd nodes after the first even node and move them to the end.



#include <stdio.h>
#include <stdlib.h>
struct node
{
     int data;
     struct node *next;
}*head=NULL,*temp,*endnode;
void insert(int item,int j,int n);
void segregate();
void print();
int main() {
  
    int n;
    int item,i,t,j;
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
         head=NULL;
         endnode=NULL;
         scanf("%d",&n);
         for(j=0;j<n;j++)
         {
             scanf("%d",&item);
             insert(item,j,n);
         }
         
         segregate();
           print();
         printf("\n");
    }
    return 0;
}
void insert(int item,int j,int n)
{
      if(head==NULL)
      {
           temp=(struct node*)malloc(sizeof(struct node));
           temp->data=item;
           temp->next=NULL;
           head=temp;
      }
      else
      {
          temp->next=(struct node*)malloc(sizeof(struct node));
          temp=temp->next;
          temp->data=item;
          temp->next=NULL;
          if(j==n-1)
          {
                 endnode=temp;
          }

      }
}
void segregate()
{
     struct node *current,*prev=NULL;
     struct node *end=endnode;
     temp=NULL;
     current=head;
     while(current!=NULL)
     {
           if(current->data%2!=0)
           {
                if(current->next==NULL)
                {
                    return;
                }
                else
                {
                    current=current->next;
                }
           }
           else
           {
                 break;
           }
     }
     current=head;
     while(current!=end && current->data%2!=0)
     {
            temp=current;
            current=current->next;
            endnode->next=temp;
            endnode->next->next=NULL;
            endnode=endnode->next;
            
     }
     head=current;
     if(current->data%2==0)
     {
             while(current!=end)
             {
                    if(current->data%2==0)
                    {
                           prev=current;
                           current=current->next;
                    }
                    else
                    {
                           temp=current;
                           prev->next=current->next;
                           current=current->next;
                           endnode->next=temp;
                           endnode->next->next=NULL;
                           endnode=endnode->next;
                    }
             }
     }
     else
     {
          prev=current;
     }
     if(endnode!=end && end->data%2!=0)
     {
          prev->next=end->next;
          end->next=NULL;
          endnode->next=end;
     }
     
}
void print()
{
     temp=head;
     while(temp!=NULL)
     {
         printf("%d ",temp->data);
         temp=temp->next;
     }
}


Output

 
Source: geeksforgeeks


EmoticonEmoticon