C++: Move all Even numbers before Odd numbers in Singly Linked List (Using STL)

Given a Singly Linked List, we have to modify it such that all Even numbers appear before Odd numbers. 


For eg. Given Linked List : 1, 2, 3, 4, 5, 6, 7
After Modification :             2, 4, 6, 1, 3, 5, 7

The functions used are insert(), exchangeEvenOdd(), getLastNode(), isOdd(), and printList().

The code for insert() and printList() is in previous code. Here

getLastNode()
 Node* getLastNode()
  {
    Node *node = head;
    while (node->next != nullptr)
           node = node->next;

    return node;
  }
 

isOdd()

bool isOdd(int num)
  {
    if (num % 2 != 0)
        return true;
    else
        return false;
  }
 
exchangeEvenOdd()

void LinkedList::exchangeEvenOdd()
{
  Node *node = nullptr;
  Node *lastNodeToTest = getLastNode();
  Node *tail = lastNodeToTest;

  while (isOdd(head->data) == true)
  {
    node = head;
    advance(head);
    tail->next = node;
    advance(tail);
  }

  Node *tmp = head;
  Node *curr = head;

  while (tmp->next != lastNodeToTest)
  {
    if (isOdd(curr->next->data) == true)
    {
      node = curr->next;
      curr->next = node->next;
      tail->next = node;
      advance(tail);
    }
    else
    {
      //advance "curr" and "tmp" only when next node to it is even
      advance(curr);
      advance(tmp);
    }
  }

  if (isOdd(curr->next->data) == true && tmp->next == lastNodeToTest)
  {
    node = lastNodeToTest;
    curr->next = lastNodeToTest->next;
    tail->next = lastNodeToTest;
    advance(tail);
  }
  tail->next = nullptr;
  lastNodeToTest = nullptr;
  node = nullptr;
}
 
You can view complete code on GitHub.
 
We can take help form Standard Template Librar.

std::stable_partition does same work. 
We can also use std::partiton but the output will not be the same relative order of each group.

Using STL

#include <iostream>
#include <algorithm>
#include <list>
#include <iterator>

int main()
{
    std::list<int> list {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    std::cout << "Original list : ";
    std::copy(std::begin(list), std::end(list), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    std::stable_partition(std::begin(list), std::end(list), [](int val){return val % 2 == 0;});
    std::cout << "New list      : ";
    std::copy(std::begin(list), std::end(list), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}
 
 
You can view this code on GitHub.


                                                                  
                                                                  
Reference:
http://en.cppreference.com/w/cpp/algorithm/stable_partition
http://en.cppreference.com/w/cpp/algorithm/partition




You may also like:
C++: Merge two sorted Linked List (in-place)
C++: STL Iterators
C++: Implementation of Merge Sort
C++: Reverse the Linked List (Iterative Method) program
C++: Breadth First Search program using Adjacency Matrix  

Comments