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;
}