[148] Sort List

唉～Sorting linked list 怎麼那麼難呢？！ QQ

就是說齁

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if (list1 ==NULL)

return list2;

if (list2 == NULL)

return list1;

if (list1->val < list2->val)

{

list1->next = mergeTwoLists(list1->next, list2);

return list1;

}

else

{

list2->next = mergeTwoLists(list1, list2->next);

return list2;

}

}

struct ListNode* findMiddlePre(struct ListNode* head)

{

struct ListNode *pre = NULL;

struct ListNode *fast = head;

struct ListNode *slow = head;

while (fast!= NULL && fast->next != NULL)

{

pre=slow;

slow =slow->next;

fast=fast->next;

if (fast->next != NULL)

fast=fast->next;

}

return pre;

}

struct ListNode* sortList(struct ListNode* head){

if (head == NULL || head->next == NULL)

return head;

struct ListNode *pre = findMiddlePre(head);

struct ListNode *mid = pre->next ;

pre->next = NULL;

struct ListNode *l1 , *l2;

l1 = sortList(head);

l2 = sortList(mid);

return mergeTwoLists(l1,l2);

}

然後可以再精簡成這樣！！！真是絕妙好code啊！！！（拍案叫絕）

原本另外呼叫 findMid ，但是又需要mid的pre因為要設成NULL

包進main 而不另外呼叫的好處之一是slow就可以直接拿來當mid用了！！！

BRAVO啊～～～（站起來鼓掌)

我對於我這麼才面對linked list sorting 這件事～對過去的我自己說聲安縮蕊XD

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if (list1 ==NULL)

return list2;

if (list2 == NULL)

return list1;

if (list1->val < list2->val)

{

list1->next = mergeTwoLists(list1->next, list2);

return list1;

}

else

{

list2->next = mergeTwoLists(list1, list2->next);

return list2;

}

}

struct ListNode* sortList(struct ListNode* head){

if (head == NULL || head->next == NULL)

return head;

struct ListNode *pre , *fast , *slow;

fast=head;

slow=head;

while (fast!= NULL && fast->next != NULL)

{

pre=slow;

slow =slow->next;

fast=fast->next;

if (fast->next != NULL)

fast=fast->next;

}

pre->next = NULL;

return mergeTwoLists(sortList(head),sortList(slow));

}