/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insert(ListNode*head, ListNode*node){
        if(head==NULL){ 
            node->next=NULL;
            return node;
        }
        
        ListNode*prev = NULL;
        ListNode*cur = head;
        while(cur){
            if(cur->val>node->val){
                //插入
                if(prev==NULL){
                    //插到链表头
                    node->next=head;
                    head = node;
                }
                else{
                    //插到链表中
                    node->next=prev->next;
                    prev->next=node;
                }
                return head;
            }
            else{
               prev=cur;
               cur=cur->next;
            }
        }
        //插到链表尾
        prev->next=node;
        node->next=NULL;
        return head;
    }
    
    ListNode *insertionSortList(ListNode *head) {
        if(head==NULL || head->next==NULL)return head;
        ListNode*newhead=NULL;
        ListNode*cur=head;
        ListNode*next=NULL;
        while(cur){
            next=cur->next;
            newhead=insert(newhead, cur);
            cur=next;
        }
        return newhead;
    }
};