Sort a linked list using insertion sort.

题目要求：链表的插入排序，由于没有时间复杂度的要求，可以直接循环操作。

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

转载请注明出处： 谢谢！