struct Node{
	int val;
	Node* next;
};

Node* insert(Node* p, Node* list)
{
	if(list == nullptr)
		return p;
	if(p->val > list->val)
	{
		list->next = insert(p,list->next);
		return list;
	}
	else
	{
		p->next = list;
		return p;
	}
}

Node* insertion_sort(Node *p)
{
	if(p == nullptr)
		return p;
	Node* sortedList = insertion_sort(p->next);
	p->next = nullptr;
	return insert(p,sortedList);
}

int main()
{
	return 0;
}