Sort linked list.

I found an interesting problem about the linked list and decided that I should try to solve this problem.

The problem statement was
Given a linked list: 1->9->3->8->5->7->7
 

 Find the pattern in the above linked link
 sort the linked list.

BTW, The pattern is odd elements in the linked list are in increasing order and even elements are decreasing order.

Sorting the above linked list is like sorting any other linked list and we could use several known methods. But since the input is already sorted, we should not try use the property. Sorting an already sorted input is always a bad approach.

This problem can be solved in several ways, the 2 approaches that I came up with are:

Method 1:
- Point nth odd element to n+1th odd element.
- Use a stack and push all the even elements on the stack until we reach end of the list.
- Once we are reach the end of the list, we can pop the elements from stack and stick them at the end of the linked list.
- Done

Method 2:
1) Again, Point nth odd element to n+1th odd element.  ( Even_list )
2) Save the next even element, so we dont loose it when we perform the step 1)
3) Now point n+1th even element to nth even element. ( Odd_list )
4) Merge odd_list  and Even_list
5) Done

Here is the code for Method 2 in C++.

#include<iostream>
#include<assert.h>
#include<fstream>

using namespace std;

class Node {
  public:
    Node( int value );
    int data;
    Node* next;
};

Node::Node( int value ) {
  data = value;
  next = NULL;
};

class List {

public:
  void add_node( int value );
  void print_list();
  void sort_list();
  List();

private:

  Node* head;
  Node* end;

  void _merge_lists( Node* &head,  Node* &even_list, Node* &odd_list );
  void _print_list( Node *iter);
  void _sort_list( Node * &subroot, Node * &even_list, Node* &odd_list, int &count ) ;
  void _merge( Node* &subroot, Node* &even_list, Node* &odd_list );
};

List::List() {
  head = NULL;
  end = head;
};

void List::add_node( int val ) {

  Node* new_node = new Node( val );

  if( head == NULL ) {
    head = new_node;
    end = head;
  } 
  else {
    end->next = new_node;
    end = end->next;
  }
}

void List::print_list() {
  Node* iter  = head;
  _print_list( iter );
}

void List::_print_list( Node *iter ) {
  while( iter != NULL ){
    printf( "%d", iter->data);
    if ( iter->next != NULL )
      printf("->");
    iter = iter->next;
  }
  printf("\n");
}

void List::_merge_lists( Node* &head, Node* &even_list, Node* &odd_list ) {

  assert( even_list!= NULL );
  assert ( head != NULL );

  if ( odd_list != NULL && even_list->data > odd_list->data ) {
    head = odd_list;
    odd_list = odd_list->next;
  }
  else {
    head = even_list;
    even_list = even_list->next;
  }

  Node* subroot = head;
  _merge( subroot, even_list, odd_list );
}

void List::_merge( Node* &subroot, Node* &even_list, Node* &odd_list ) {

  assert( subroot != NULL );

  if ( odd_list == NULL && even_list == NULL ) {
    return;
  }
  if( odd_list == NULL ) {
    subroot->next =  even_list;
    return;
  }
  else {
    if ( even_list == NULL ) {
    subroot->next = odd_list;
    return;
    }
    else {
      assert ( even_list != NULL );
      assert( odd_list != NULL );

      if ( even_list->data < odd_list->data ) {
    subroot->next = even_list;
    even_list = even_list->next;
      }
      else {
    subroot->next = odd_list;
    odd_list = odd_list->next;
      }
      subroot = subroot->next;
      _merge( subroot, even_list, odd_list );
    }
  }
}

void List::sort_list(){
  
  Node* even_list = NULL;
  Node* odd_list = NULL;
  int count = 0;
  _sort_list( head, even_list, odd_list, count );  

  even_list = head;
  _merge_lists( head, even_list, odd_list );
}


void List::_sort_list( Node* &subroot, Node* &even_list, Node* &odd_list, int &count ) {

  if ( subroot == NULL ) {
    return;
  }

  Node* next_node = subroot->next;

  // even elements, 0,2,.....
  if ( count % 2 == 0 ) {
    if ( even_list == NULL ) {
      even_list = subroot;
      even_list->next = NULL;
    }
    else {
      even_list->next  = subroot;
      even_list = even_list->next;
      even_list->next = NULL;
    }
  }
  // Odd element
  else {
    if ( odd_list == NULL ) {
      odd_list = subroot;
      odd_list->next = NULL;
    }
    else {
      subroot->next = odd_list;
      odd_list = subroot;
    }
  }
  _sort_list( next_node, even_list, odd_list, ++count );
}

Feel free to comment if there are any bugs in the code or it does not work on a given case.