Insertion Sort List

#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <utility>
#include <cctype>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};


ListNode* buildList(){
	cout<<"Please input the list length:"<<endl;
	int n;
	cin>>n;
	cout<<"Please input the value of the list:"<<endl;
	ListNode dumy(-1);
	ListNode *p = &dumy;
	for(int i=0;i < n; ++i){
		int val;
		cin>>val;
		p->next = new ListNode(val);
		p = p->next;
	}	
	return dumy.next;
}

void destory(ListNode *head){
	ListNode *p = head;
	while( p ){
		head = p->next;
		delete p;
		p = head;
	}
}

void printList(ListNode *head)
{
	ListNode *p = head;
	while( p ){
		cout<<p->val<<"\t";
		p = p->next;
	}
	cout<<endl;
}

ListNode *insertionSortList(ListNode *head) {
	if( head == NULL) return head;
	ListNode dumy(-1);
	dumy.next = head;
	ListNode *last = head->next;
	head->next = NULL;
	
	while( last ){
		ListNode *p = last;
		last = last->next;
		p->next = NULL;
		ListNode* pre = &dumy;
		while( pre->next ){
			if( pre->next->val <= p->val)
				pre = pre->next;
			else{
				p->next = pre->next;
				pre->next = p;
				break;
			}
		}
		if( pre->next == NULL){
			pre->next = p;
		}
	}
	return dumy.next;
}

int main(){
	while( 1 ){
		ListNode* head = buildList();
		ListNode* res = insertionSortList(head);
		printList(res);
		destory(res);
	}
}