/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) 
    {
        if(head==NULL) return NULL;
        ListNode* phead=new ListNode(getmin(head));
        ListNode* p1=phead;
        while(head!=NULL)
        {
            ListNode* p2=new ListNode(getmin(head));
            p1->next=p2;
            p1=p2;
        }
        return phead;
    }
    int getmin(ListNode* &head)
    {
        if(head->next==NULL)
        {
            int val=head->val;
            head=NULL;
            return val;
        }
        ListNode* pre=NULL;
        int val=head->val;
        
        ListNode* p2=head;
        while(p2->next!=NULL)
        {
            if(p2->next->val<val) 
            {
                val=p2->next->val;
                pre=p2;            
            }
            p2=p2->next;
        }
        if(pre==NULL)
        {
            head=head->next;
        }
        else
            pre->next=pre->next->next;
        return val;
    }
};