用插入排序对链表排序
您在真实的面试中是否遇到过这个题？
Yes
样例
Given 1->3->2->0->null, return 0->1->2->3->null
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The head of linked list.
*/
//为了化简 ，这是是一个带有头节点的 head节点
//将node插入道head上面，并且保持从小到大的顺序
void insert(ListNode *head,ListNode *node){
node->next=NULL;
if(head->next==NULL){
head->next=node;
return ;
}
ListNode * pre=head;
ListNode * p=head->next;
while(p!=NULL){
if(p->val>node->val){
node->next=p;
pre->next=node;
return ;
}
else{
p=p->next;
pre=pre->next;
}
}
pre->next=node;
}
ListNode *insertionSortList(ListNode *head) {
// write your code here
ListNode * newhead=new ListNode();
ListNode * p=head;
while(p!=NULL){
ListNode * node =p;
p=p->next;
insert(newhead,node);
}
return newhead->next;
}
};
