題目連結
struct ListNode *MergeSortList(struct ListNode *head1, struct ListNode *head2)
{
struct ListNode *p1, *p2, *p, *temp;
p = (struct ListNode *)malloc(sizeof(struct ListNode));
temp = p; //暫存合并後的連結清單的頭結點
p1 = head1;
p2 = head2;
while (p1&&p2)
{
if (p1->val <= p2->val)
{
p->next = p1;
p1 = p1->next;
}
else
{
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1)
p->next = p1;
else
p->next = p2;
p = temp->next;
return p;
}
struct ListNode *MergeSort(struct ListNode *head)
{
struct ListNode *fast, *slow, *slowPrev, *leftHalf, *rightHalf;
fast = slow = head;
if (!head || !head->next)
return head;
while (fast&&fast->next)
{
fast = fast->next->next;
slowPrev = slow;
slow = slow->next;
}
slowPrev->next = NULL;
leftHalf = MergeSort(head);
rightHalf = MergeSort(slow);
return MergeSortList(leftHalf, rightHalf);
}
struct ListNode *sortList(struct ListNode *head)
{
if (!head || !head->next)
return head;
return MergeSort(head); //歸并排序,保證算法複雜度為O(nlog(n))
}