/**

 * 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,int num){

        ListNode *node = new ListNode(num);

        if(head==NULL || num <= head->val){

            node->next=head;

            return node;

        }

        ListNode *pre = head;

        ListNode *tail = head->next;

        while(tail!=NULL && num > tail->val){  // 一定要注意tail!=NULL 先决条件

                pre= tail;

                tail=tail->next;

        }

        node->next = pre->next;

        pre->next = node;

        return head;

    }

    ListNode* insertionSortList(ListNode *head){

        if(head==NULL || head->next==NULL) return head;

        ListNode *tmp = head;

        ListNode* ans=NULL;

        while(tmp!=NULL){

            ans = insert(ans,tmp->val);

            tmp =tmp->next;

        }

        return ans;

    }

};