[147] Insertion Sort List

不得了！！！

竟然只有卡了一個while 比完大小忘記break，

其它的一次ok !!! 我要落淚了我

雖然好像沒有很快，但是管它的 XD

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* insertionSortList(struct ListNode* head){

struct ListNode* newhead=NULL;

struct ListNode* oldP;

struct ListNode* newP;

while(head !=NULL)

{

oldP=head;

head=head->next;

oldP->next=NULL;

//find new location

if (newhead==NULL)

{

newhead=oldP;

continue;

}

newP = newhead;

struct ListNode* pre;

pre= newP;

while(newP!=NULL)

{

if (oldP->val > newP->val)

{

pre=newP;

newP=newP->next;

}

else

break;

}

oldP->next=newP;

if (newP==newhead)

newhead=oldP;

else

pre->next=oldP;

}

return newhead;

}