#include <iostream>

using namespace std;

typedef struct lnode{
        int data;
        struct lnode* next;
}lNODE;

typedef struct node{
        char data;
        struct node* next;
}NODE;

typedef struct list{
        NODE* head;
        NODE* tail;
}LIST;

typedef struct student{
        LIST first;
        int grade;
} STUDENT;

STUDENT unScramble(LIST lst);
void deleteLnode(LIST &lst, NODE *lnode, NODE* saver);
void makeEmptyList(LIST &lst);
void insertNodeToEndList(LIST &lst, NODE *newTail);
bool isEmptyList(LIST lst);
void insertDataToEndList(LIST &lst, char data);
NODE* creatNewListNode(char data, NODE* next);
void printList(LIST lst);

void main()
{
        STUDENT student;
        LIST lst;
		NODE* saver;
		makeEmptyList(lst);////////////
        insertDataToEndList(lst, 'm');
		insertDataToEndList(lst, '9');
        insertDataToEndList(lst, 'u');
        insertDataToEndList(lst, 'l');
		insertDataToEndList(lst, '4');
        insertDataToEndList(lst, 'l');
        insertDataToEndList(lst, 'y');

		makeEmptyList(student.first);
        student = unScramble(lst);

        cout << "The unscramble list is: ";

        printList(student.first);

		while(isEmptyList(lst) == false)
        {
			saver = lst.head;
			lst.head = lst.head->next;
			delete[] saver;
        }

        system("pause");
}

STUDENT unScramble(LIST lst)
{
        STUDENT student;
        student.grade = 0;
        makeEmptyList(student.first);
        NODE *curr, *saver;
        curr = lst.head;


        while (curr != NULL)
        {

                if (47 < curr->data && curr->data < 58)
                {
                        student.grade *= 10;
                        student.grade += (curr->data);

						saver = curr;
						curr = curr->next;
                        deleteLnode(lst, saver, NULL);
                }

                else
				{		saver = curr->next;//////////////////////
                        insertNodeToEndList(student.first, curr);
                        curr = saver;////////
                }
        }
        return student;
}

void deleteLnode(LIST &lst, NODE *lnode, NODE* saver)
{
        if (lst.head == lnode && lst.tail == lnode)
        {
                lst.head = lst.tail = NULL;
        }

        else if (lst.head == lnode)
        {
                lst.head = lnode->next;
        }

        else if (lnode->next->next == NULL)
        {
                lnode->next = NULL;
                lst.tail = lnode;
        }

        else
        {
                saver = lnode->next;
        }
}

void makeEmptyList(LIST &lst)
{
        lst.head = lst.tail = NULL;
}

void insertNodeToEndList(LIST &lst, NODE *newTail)
{
        if (isEmptyList(lst) == true)
        {
                lst.head = lst.tail = newTail;
        }

        else
        {
                lst.tail->next = newTail;
                lst.tail = newTail;
        }

        lst.tail->next = NULL;
}

bool isEmptyList(LIST lst)
{
        if (lst.head == NULL)
                return true;

        else
                return false;
}

void insertDataToEndList(LIST &lst, char data)
{
        NODE *newTail;
        newTail = creatNewListNode(data, NULL);
        insertNodeToEndList(lst, newTail);
}

NODE* creatNewListNode(char data, NODE* next)
{
        NODE* res;
        res = new NODE;
        res->data = data;
        res->next = next;

        return res;
}

void printList(LIST lst)
{
        NODE* curr = lst.head;

        while (curr != NULL)
        {
                cout << curr->data << " ";
                curr = curr->next;
        }
}