[LeetCode 题解]: Insertion Sort List

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