LeetCode148—Sort List-蒲公英云

LeetCode148—Sort List

原题

原题链接

Sort a linked list in O(n log n) time using constant space complexity.

Subscribe to see which companies asked this question

分析

O(nlogn) 时间复杂度的排序就那么几种，快排、归并排序、堆排序。这题我用归并排序。

归并排序的思路是分而治之，传统在以数组或容器作为数据结构的归并排序算法中，我们可以用左右边界的索引来对待排序列不断的向下“分”，显然索引访问在链表这里就行不通了。

如何对链表进行“分” 操作？
1.找到链表的中点（节点个数为偶数时使用返回靠左的节点作为中点返回）。
2.记录中点节点的下一个位置（作为右半序列的头指针）
3.将中点的next置为NULL，这样原链表就被砍成两节了。
4.循环进行前3步，直到链表被打散成一个一个的节点。

上述四步就完成了分操作，接下来要合并，也就是排序：
这一步就简单了，其本质就是将两个有序链表合并到一个有序链表中去。

代码

class Solution {
private:
    ListNode* findMid(ListNode* list);
    ListNode* MergeSort(ListNode* list);
    ListNode* Merge(ListNode* left,ListNode*right);
public:
    ListNode* sortList(ListNode* head) {
        return MergeSort(head);
    }
};
ListNode* Solution::findMid(ListNode *list)
{
    if(NULL==list)
        return list;
    ListNode* slow=list;
    ListNode* quick=list->next;
    while(quick&&quick->next)
    {
        slow=slow->next;
        quick=quick->next->next;
    }
    return slow;
}
ListNode* Solution::MergeSort(ListNode* list)
{
    if(list==NULL||list->next==NULL)
        return list;
    ListNode* mid = findMid(list);
    ListNode* right=mid->next;
    mid->next=NULL;
    list=MergeSort(list);
    right=MergeSort(right);
    return Merge(list,right);
}
ListNode* Solution::Merge(ListNode*left,ListNode*right)
{
    ListNode* result=new ListNode(0);
    ListNode * p=result;
    while(left&&right)
    {
        if(left->val<=right->val)
        {
            p->next=left;
            p=left;
            left=left->next;
        }
        else
        {
            p->next=right;
            p=right;
            right=right->next;
        }
    }
    if(NULL!=left)
        p->next=left;
    if(NULL!=right)
        p->next=right;
    return result->next;
}