#define SinglyLinkedListLibrary
#include <iostream>
// 12_04_2020
using namespace std;

//struct node{
//	int data;
//	node* pNext;
//};

//
//void addFirst(node*& pH, int k) {
//	node* p = new node;
//	if (p == nullptr) exit(0);//exit when memory full
//	p->data = k;
//	p->pNext = nullptr;
//
//	p->pNext = pH;
//	pH = p;//update pH
//}
//
//void displayAll(node* pH) {
//	if (pH == nullptr) {
//		cout << "Empty list.\n";
//		return;
//	}
//	cout << "List:\n";	
//	while (pH != nullptr) {
//		cout << pH->data << "\t";
//		pH = pH->pNext;
//	}
//	cout << endl;
//}
//
//void freeAllNode(node*& pH) {	
//	while (pH!=nullptr) {
//		node* cur = pH;
//		pH = pH->pNext;
//		delete cur;
//	}
//}
//
//bool insertAfterX(node* pH, int k, int x) {
//	if (pH == nullptr) return false;
//	bool IsFound = false;
//	while (pH != nullptr && !IsFound) {
//		if (pH->data == x) {
//			node* p = new node;
//			p->data = k;
//
//			p->pNext = pH->pNext;
//			pH->pNext = p;
//			IsFound = true;
//		}
//		pH = pH->pNext;
//	}
//	return IsFound;
//}
//
//bool insertBeforeX(node*& pH, int k, int x) {
//	if (pH == nullptr) return false;
//
//	if (pH->data == x) {
//		node* p = new node;
//		p->data = k;
//		p->pNext = pH;
//		pH = p;
//		return true;
//	}
//
//	bool flag = false;
//	node* cur = pH;
//	while (pH->pNext != nullptr && !flag) {
//		if (pH->pNext->data == x) {
//			node* p = new node;
//			p->data = k;
//			p->pNext = pH->pNext;
//			pH->pNext = p;
//			flag = true;
//		}
//		pH = pH->pNext;
//	}
//	pH = cur;
//	return flag;	
//}
//
//void deleteFirstX(node*& pH,int x){
//	if (pH == nullptr) return;
//
//	if (pH->data == x) {
//		node* cur = pH;
//		pH = pH->pNext;
//		delete cur;
//		return;
//	}
//
//	node* cur = pH;
//	while (pH->pNext!=nullptr) {
//		if (pH->pNext->data == x) {
//			node* temp = pH->pNext;
//			pH->pNext = pH->pNext->pNext;
//			delete temp;
//			pH = cur;
//			return;
//		}
//		pH = pH->pNext;
//	}
//	pH = cur;
//}
//
//void deleteAllX(node*& pH, int x) {
//	if (pH == nullptr) return;
//
//	while (pH->data == x) {//x is first node
//		node* cur = pH;
//		pH = pH->pNext;
//		delete cur;		
//		if (pH == nullptr) return;//all list is x
//	}
//	
//
//	node* firstNode = pH;
//	while (pH->pNext!= nullptr) {
//		if (pH->pNext->data == x) {
//			node* cur = pH->pNext;			
//			pH->pNext = pH->pNext->pNext;// 1 2 x 3 4 ______ pH->Next=x and now pH->Next=3, so don't need pH=pH->pNext;
//			delete cur;
//			if (pH->pNext == nullptr) {// x is final node
//				pH = firstNode;
//				return;
//			}
//		}
//		else {
//			pH=pH->pNext;
//		}
//	}
//	pH = firstNode;
//}
//
//void creatOrderList(node* pH) {
//	if (pH == nullptr) return;
//	node* cur = pH;//cur is i varriable, pH is j varriable
//
//	while (pH != nullptr) {
//		while (pH != nullptr) {
//			if (pH->data < cur->data) {
//				swap(pH->data, cur->data);// swap data
//			}
//			pH = pH->pNext;
//		}
//		cur = cur->pNext; // ++i
//		pH = cur; // reinitial j=i => ++j
//	}
//}

 //17_04_2020

struct node {
    int data;
    node* next;
};

node* getNode(int k) {//
    node* p = new node;
    p->data = k;
    p->next = nullptr;
    return p;
}

void addFirst(node*& pH, int k) {
    node* p = getNode(k);
    if (pH == nullptr)
        pH = p;
    else {
        p->next = pH;
        pH = p;
    }
}

void showAllList(node* pH) {
    cout << "\n";
    while (pH != nullptr) {
        cout << pH->data << "\t";
        pH = pH->next;
    }
    cout << endl;
}

void freeAllNode(node*& pH) {
    node* cur = nullptr;
    while (pH != nullptr) {
        cur = pH;
        pH = pH->next;
        delete cur;
    }
}

void addToLastList(node*& pH, int k) {
    if (pH == nullptr) {
        node* p = getNode(k);
        pH = p;
        return;
    }
    node* cur = pH;
    while (cur->next!= nullptr)
        cur = cur->next;
    node* p = getNode(k);
    cur->next = p;
}

void insertAfterX(node* pH, int x, int k) {
    if (pH == nullptr) return;
    bool flag = false;
    while (!flag && pH != nullptr)
    {
        if (pH->data == x) {
            node* p = getNode(k);
            p->next = pH->next;
            pH->next = p;
            flag = true;
        }
        pH = pH->next;
    }
}

void insertBeforeX(node*& pH, int x, int k) {
    if (pH == nullptr) return;

    if (pH->data == x) {
        addFirst(pH, k);
        return;
    }

    bool flag = false;
    node* cur = pH;

    while (!flag && pH->next != nullptr) {
        if (pH->next->data == x) {
            node* p = getNode(k);

            p->next = pH->next;
            pH->next = p;

            flag = true;
        }
        pH = pH->next;
    }
    pH = cur;
}

void delAllX(node*& pH, int x) {
    if (pH == nullptr) return;

    while (pH != nullptr && pH->data == x) {
        node* cur = pH;
        pH = pH->next;
        delete cur;
    }

    node* cur = pH;
    while (pH != nullptr && pH->next != nullptr) {
        if (pH->next->data == x) {
            node* p = pH->next;
            pH->next = pH->next->next;//pH=pH->pNext
            delete p;
        }
        else {
            pH = pH->next;
        }
    }
    pH = cur;
}

void delFirstX(node*& pH, int x) {
    if (pH == nullptr) return;

    if (pH->data == x) {//first node =x
        node* p = pH;
        pH = pH->next;
        delete p;
        return;
    }

    bool flag = false;
    node* cur = pH;
    while (!flag && pH != nullptr && pH->next != nullptr)
    {
        if (pH->next->data == x) {
            flag = true;
            node* p = pH->next;
            pH->next = pH->next->next;
            delete p;
        }
        else {
            pH = pH->next;
        }

    }
    pH = cur;
}

int lengthList(node* pH) {//count number of elements of link list
    int k = 0;
    while (pH != nullptr) {
        ++k;
        pH = pH->next;
    }
    return k;
}

void creatOrderList(node*& pH) {
    int x;

    while (true) {
        cout << "enter x: \n";
        cin >> x;
        if (x == 0) return;// 4 6 5 

        if (pH == nullptr || pH->data > x) {
            node* p = getNode(x);
            p->next = pH;
            pH = p;
        }
        else {
            node* cur = pH;
            while (cur->next != nullptr && cur->next->data < x)
                cur = cur->next;
            node* p = getNode(x);
            p->next = cur->next;
            cur->next = p;
        }
    }

}

void mergeTwoOrderedList(node*& pH1, node*& pH2) {
    if (pH1 == nullptr) {
        pH1 = pH2;
        return;
    }
    while (pH1 != nullptr && pH2 != nullptr && pH1->data > pH2->data) {
        node* temp = pH2;
        pH2 = pH2->next;
        temp->next = pH1;
        pH1 = temp;
    }

    node* cur1 = pH1;
    node* cur2 = pH2;
    while (cur2 != nullptr) {
        while (cur1->next != nullptr && cur1->next->data < cur2->data)
            cur1 = cur1->next;
        node* temp = cur2;
        cur2 = cur2->next;
        temp->next = cur1->next;
        cur1->next = temp;
    }

}

void removeAllX(node*& pH, int x) {
    if (pH == nullptr) return;

    while (pH != nullptr && pH->data == x) {
        node* cur = pH;
        pH = pH->next;
        delete cur;
    }

    node* cur = pH;
    while (cur != nullptr && cur->next != nullptr) {
        if (cur->next->data == x) {
            node* temp = cur->next;
            cur->next = cur->next->next;
            delete temp;
        }
        else {
            cur = cur->next;
        }
    }
}

void delNodeAfter(node* pH) {
    if (pH == nullptr || pH->next == nullptr) return;

    node* cur = pH->next;
    pH->next = pH->next->next;
    delete cur;
}

void removeDuplicate(node* pH) {
    node* cur = pH, * var,*dup;
    /*The variables varand cur represent the variables iand j in the nested loop for (i) for (j)*/
 /*   Consider each element from cur = pH to the end of the list.
        For each element we compare from cur to the end of ds through var variable, 
        if var->data = cur->data then delete node at var and continue loop cur = cur->next*/
    while (cur != nullptr && cur->next != nullptr) {
        var = cur;// j=i
        while (var->next!=nullptr) {
            if (var->next->data == cur->data) {
                dup = var->next;
                var->next = var->next->next;// var=var->next;
                delete dup;
            }
            else {
                var = var->next;
            }
        }
        cur = cur->next;
    }

}

node* reverseList(node* pH) {
    node* p=nullptr, * cur;
    while (pH != nullptr) {
        cur = pH;
        pH = pH->next;
        cur->next = p;
        p = cur;
    }
    return p;
}

void insertEvenNum(node* &pH){
    if (pH == nullptr) return;

    int x = 2;
    node* p = getNode(x);
    p->next = pH;
    pH = p;//insert first node
    

    node* cur = pH;// 1 2 3 5
    cur = cur->next;// skip node have value 2
    while (cur!=nullptr&&cur->next!=nullptr) {
        x = x + 2;
        node* p = getNode(x);
        p->next = cur->next;//insert even num after node cur
        cur->next = p;

        cur = cur->next->next;// skip node have just inserted
    }
}

void insertSortedList(node* &pH,int x){
    if (pH == nullptr || pH->data > x) {
        addFirst(pH, x);
        return;
    }

    node* cur = pH;
    while (cur->next != nullptr && cur->next->data < x)
        cur = cur->next;
    node* p = getNode(x);
    p->next = cur->next;
    cur->next = p;
}
  
  int main() {
    node* pH = nullptr;
	int k = 1;

	//while (k != 0) {
	//	cout << "Enter value (0 to exit):\n";
	//	cin >> k;
	//	if (k != 0) addToLastList(pH, k);
	//}
	//showAllList(pH);
	creatOrderList(pH);
	insertSortedList(pH, 5);
	showAllList(pH);
	

	return 0;
}