[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));

}

[20250923 update]

果然一陣子沒leetcode , 就寫出了垃圾...(痛哭again) 留在這裡以茲紀念, 都是自己的孩子啊～～～（緊摟）之後再更新一下, 應該就會跟上面長一樣了吧......

struct ListNode* sortList(struct ListNode* head);

struct ListNode* split(struct ListNode* l1,struct ListNode* l2) {

printf("%d %d\n", l1->val, l2->val);

struct ListNode* m1;

struct ListNode* m2;

struct ListNode* ret;

struct ListNode* ptr;

m1 = sortList(l1);

m2 = sortList(l2);

if (m1 == NULL)

return m2;

if (m2 == NULL)

return m1;

if (m1->val < m2->val)

{

ret = m1;

m1 = m1->next;

}

else

{

ret = m2;

m2 = m2->next;

}

ptr = ret;

while (ptr != NULL)

{

if (m1 ==NULL)

{

ptr-> next = m2;

m2 = m2->next;

break;

}

if (m2 ==NULL)

{

ptr-> next = m1;

m1 = m1->next;

break;

}

if (m1->val < m2->val)

{

ptr ->next = m1;

m1 = m1 ->next;

}

else

{

ptr->next = m2;

m2 = m2->next;

}

ptr = ptr->next;

}

return ret;

}

struct ListNode* sortList(struct ListNode* head) {

if (head== NULL)

return NULL;

if (head->next == NULL)

return head;

struct ListNode* fast=head;

struct ListNode* slow=head;

struct ListNode* pre;

struct ListNode* ret;

while (fast != NULL)

{

fast = fast-> next;

if (fast == NULL)

break;

fast = fast->next;

pre = slow;

slow = slow->next;

}

pre->next = NULL;

ret = split(head, slow);

return ret;

}