#include <iostream>
#include <string>

struct listNode
{
   char data;
   struct listNode *nextPtr;
};
typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert( ListNodePtr *, char );
char remove( ListNodePtr *, char );
Node* mergelist(Node *head1, Node *head2);
void splitList(Node *head, Node **Ahead, Node **Dhead);
void reverselist(Node *&head);
int isEmpty( ListNodePtr );
void printList( ListNodePtr );
void instructions( void );

int main()
{
ListNodePtr startPtr = NULL;
int choice;
char item;
instructions();
cout << ( "? " );
cin >> ( "%d", &choice );
while ( choice != 5 ) {
switch ( choice ) {
case 1:
cout <<  "Enter a character: " ;
cin >>  "\n%c" >> &item ;
insert( &startPtr, item );
printList( startPtr );
break;
case 2:
if ( !isEmpty( startPtr ) ) {
cout << "Enter character to be deleted: " ;
cin >>  "\n%c" >> &item ;
if ( delete( &startPtr, item ) ) {
cout << "%c deleted.\n" << item ;
printList( startPtr );
}
else
cout << "%c not found.\n\n" << item ;
}
else
cout << "List is empty.\n\n" ;
break;
case 3:
sort( &head);
splitList(*head, &Ahead, &Dhead);
printList(head);
break;
case 4:
sort( &head);
reverselist(Dhead);
printList(head);
break;
default:
cout << "Invalid choice.\n\n" ;
instructions();
break;
}
cout << "? " ;
cin >> "%d" >> &choice ;
}
cout << "End of run.\n"  ;
return 0;
}
/* Print the instructions */
void instructions( void )
{
cout << "Enter your choice:\n" 
" 1 to insert an element into the list.\n"
" 2 to delete an element from the list.\n"
" 3 to sort an element from the list.\n"
" 4 to reverse an element from the list.\n"
" 5 to end.\n" ;
}
/* Insert a new value into the list in sorted order */
void insert( ListNodePtr *sPtr, char value )
{
ListNodePtr newPtr, previousPtr, currentPtr;
newPtr = malloc( sizeof( ListNode ) );
if ( newPtr != NULL ) { /* is space available */
newPtr->data = value;
newPtr->nextPtr = NULL;
previousPtr = NULL;
currentPtr = *sPtr;
while ( currentPtr != NULL && value > currentPtr->data ) {
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}
if ( previousPtr == NULL ) {
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
}
else {
previousPtr->nextPtr = newPtr;
newPtr->nextPtr = currentPtr;
}
}
else
cout << "%c not inserted. No memory available.\n" << value ;
}
/* Delete a list element */
char delete( ListNodePtr *sPtr, char value )
{
ListNodePtr previousPtr, currentPtr, tempPtr;
if ( value == ( *sPtr )->data ) {
tempPtr = *sPtr;
*sPtr = ( *sPtr )->nextPtr;
free( tempPtr );   
return value;
}
else {
previousPtr = *sPtr;
currentPtr = ( *sPtr )->nextPtr;
while ( currentPtr != NULL && currentPtr->data != value ) {
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr; /* ... next node */
}
if ( currentPtr != NULL ) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free( tempPtr );
return value;
}   
}
return '\0';
}
* Return 1 if the list is empty, 0 otherwise */
int isEmpty( ListNodePtr sPtr )
{
return sPtr == NULL;
}
/* Print the list */
void printList( ListNodePtr currentPtr )
{
if ( currentPtr == NULL )
cout <<"List is empty.\n\n" ;
else {
cout <<  "The list is:\n"  ;
while ( currentPtr != NULL ) {
cout <<  "%c --> " << currentPtr->data ;
currentPtr = currentPtr->nextPtr;
}
cout <<  "NULL\n\n" ;
system("pause");
}
/* Sort a list element */
void sort(Node **head)
{
// Split the list into lists
Node *Ahead, *Dhead;
splitList(*head, &Ahead, &Dhead);
  
// Reverse the descending linked list
reverselist(Dhead);
  
// Merge the two linked lists
*head = mergelist(Ahead, Dhead);
}
Node* newNode(int key)
{
Node *temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
  
// A utility function to reverse a linked list
void reverselist(Node *&head)
{
Node* prev = NULL, *curr = head, *next;
while (curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}
  
// A utility function to print a linked list
void printList(Node *head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
  
// A utility function to merge two sorted linked lists
Node *mergelist(Node *head1, Node *head2)
{
// Base cases
if (!head1) return head2;
if (!head2) return head1;
  
Node *temp = NULL;
if (head1->data < head2->data)
{
temp = head1;
head1->next = mergelist(head1->next, head2);
}
else
{
temp = head2;
head2->next = mergelist(head1, head2->next);
}
return temp;
}
void splitList(Node *head, Node **Ahead, Node **Dhead)
{
// Create two dummy nodes to initialize heads of two linked list
*Ahead = newNode(0);
*Dhead = newNode(0);
  
Node *ascn = *Ahead;
Node *dscn = *Dhead;
Node *curr = head;
  
// Link alternate nodes
while (curr)
{
// Link alternate nodes of ascending linked list
ascn->next = curr;
ascn = ascn->next;
curr = curr->next;
  
// Link alternate nodes of descending linked list
if (curr)
{
dscn->next = curr;
dscn = dscn->next;
curr = curr->next;
}
}
  
ascn->next = NULL;
dscn->next = NULL;
*Ahead = (*Ahead)->next;
*Dhead = (*Dhead)->next;
}
}
}