Group even and odd numbers in a linked list

By | May 29, 2016

Group even and odd numbers in a linked list

Problem statement for segregating even and odd numbers in a linked list:

Given a singly linked list, you have to group the even numbers and the odd numbers. The even numbers’ group must be ahead the group of odd numbers. Also, each number in the groups must be in the same order as they appear in the list.

Grouping even and odd numbers in a linked list Example:

Consider a singly linked list:
1-> 2-> 9-> 3-> 8-> 6-> 4-> 7-> NULL
Resultant list should be
2-> 8-> 6-> 4-> 1-> 9-> 3-> 7-> NULL

Solution to group even and odd numbers of a linked list:

Method 1:

Algorithm to group even and odd numbers of a linked list:

  1. Place a pointer to the last node of the list.
  2. Traverse the list from the first node to the last node.
    1. If the data of traversed node is an even number, move to the next node.
    2. If data is an odd number, move the node to the end of the list.

Solution in C++ for groupping even and odd numbers of a linked list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}

/*Function to group even and
odd numbers in a linked list*/
void group_even_odd(node **head)
{
   if(*head == NULL)
   {
      cout<<"\nEmpty list.";
      exit(0);
   }
   
   node *last = *head;
   node *first_even_node = NULL;
   int n = 0;

   /*Loop finds the last node,
   the first even node and sets 
   n = total nodes-1*/
   while(last->next != NULL)
   {
      n++;
      if(first_even_node == NULL && (last->data) % 2 == 0)
         first_even_node = last;
      last = last->next;
   }
   
   node *prev = NULL;
   node *curr = *head;
   node *temp;
   int i;
   
   /*Loop traverses each node of list*/
   for(i=0 ; i<=n ; i++)
   {
      /*If data of node is odd*/
      if((curr->data)%2 != 0)
      {	
         temp = curr->next;
         
         /*If curr is not head node*/
         if(prev != NULL)
            prev->next = curr->next;
         
         /*Moving curr to end of list*/
         curr->next = NULL;
         last->next = curr;
         last = curr;
         curr = temp;
      }
      
      /*If node data is even*/
      else
      {
         /*Moving to next node*/
         prev = curr;
         curr = curr->next;
      }
   }
   
   /*Updating head*/
   *head = first_even_node;
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL;
  InsFront(&head, 7);
  InsFront(&head, 4);
  InsFront(&head, 6);
  InsFront(&head, 8);
  InsFront(&head, 3);
  InsFront(&head, 9);
  InsFront(&head, 2);
  InsFront(&head, 1);
  
  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Calling function to group
  even and odd nodes of list*/
  group_even_odd(&head);
  
  cout<<"\nResultant Linked list is:\n";
  printList(head);
 
  return 0;
}

Output:

Created Linked list is:
1-> 2-> 9-> 3-> 8-> 6-> 4-> 7-> NULL
Resultant Linked list is:
2-> 8-> 6-> 4-> 1-> 9-> 3-> 7-> NULL

Time Complexity of groupping even and odd numbers of a linked list: O(N)
where N is the total number of nodes in the given linked list.


Method 2:

Algorithm to group even and odd numbers of a linked list:

  1. Traverse each node of linked list.
    1. If node data is an even number, move to next node.
    2. If node is an odd number, move it to another list which contains all odd nodes.
  2. Repeat for all nodes in list.
  3. Combine the two lists.

Solution in C++ for groupping even and odd numbers of a linked list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes at end of Linked List*/
void InsEnd(node **head, node **last, int data)
{
    node *temp = new node;
    temp->data = data;
    temp->next = NULL;
 
    /*If list is empty.*/
    if((*head) == NULL)
    {
        /*The first node is the head and last node*/
        *head = temp; 
        *last = temp;
    }
 
    else
    {
    	(*last)->next = temp;
    	*last = temp;
    }
}
 
/*Function to group even and
odd numbers in a linked list*/
void group_even_odd(node **head)
{
   if(*head == NULL)
   {
      cout<<"\nEmpty list.";
      exit(0);
   }
   
   node *last = NULL;
   node *curr = *head;
   node *odd_list_head = NULL;
   node *prev = NULL;
   node *temp;
   
   /*Traverse list*/
   while(curr != NULL)
   {
      /*If node has odd value*/
      if((curr->data)%2 != 0)
      {
         /*Insert into another list*/
         InsEnd(&odd_list_head,&last,curr->data);
         curr = curr->next;
      }
      
      /*If node has even value*/
      else
         /*Break loop. curr points
         to first even node*/
         break;
   }
   
   /*If list has no even node*/
   if(curr == NULL)
      return;
   
   /*head points to first even node*/
   *head = curr;
   
   /*Traverse remaining list*/
   while(curr != NULL)
   {		
      /*If node has odd value*/
      if((curr->data)%2 != 0)
      {
         /*Insert into another list*/
         InsEnd(&odd_list_head,&last,curr->data);
         
         /*Delete odd node from list*/
         temp = curr;
         prev->next = curr->next;
         delete temp;
         curr = prev->next;
      }
      
      /*If node has even value*/
      else
      {
         /*Move to respective next nodes*/
         prev = curr;
         curr = curr->next;
      }
   }
   
   /*Combine even and odd lists*/
   prev->next = odd_list_head;
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL,*last = NULL;
  InsEnd(&head, &last,1);
  InsEnd(&head, &last,2); 
  InsEnd(&head, &last,9);
  InsEnd(&head, &last,3);
  InsEnd(&head, &last,8);
  InsEnd(&head, &last,6);
  InsEnd(&head, &last,4);
  InsEnd(&head, &last,7);

  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Calling function to group
  even and odd nodes of list*/
  group_even_odd(&head);
  
  cout<<"\nResultant Linked list is:\n";
  printList(head);
 
  return 0;
}

Output:

Created Linked list is:
1-> 2-> 9-> 3-> 8-> 6-> 4-> 7-> NULL
Resultant Linked list is:
2-> 8-> 6-> 4-> 1-> 9-> 3-> 7-> NULL

Time Complexity of grouping even and odd numbers of a linked list: O(N)
where N is the total number of nodes in the given linked list.