148. Sort List
給兩個single linked list請將這兩個linked list合併在一起，並且由小到大排列
思路：　
就是考merge sort
C code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* merge (struct ListNode* list1, struct ListNode* list2){
struct ListNode* res=(struct ListNode*)calloc(1,sizeof(struct ListNode));
struct ListNode* temp=res;
while (list1 && list2){
if(list1->val<list2->val){
temp->next=list1;
list1=list1->next;
}else{
temp->next=list2;
list2=list2->next;
}
temp=temp->next;
}
if (list1){
temp->next=list1;
}else{
temp->next=list2;
}
return res->next;
}
struct ListNode* sortList(struct ListNode* head) {
if (!head || !(head->next)){
return head;
}
struct ListNode* slow=head,*fast=head,*pre;
while(fast && (fast->next)){
pre=slow;
fast=fast->next->next;
slow=slow->next;
}
pre->next=NULL;
return merge(sortList(slow),sortList(head));
}
繼續騙p幣