LeetCode148—Sort List

素颜马尾好姑娘i 2022-07-15 03:16 184阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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;
    }

[Link 1]: https://leetcode.com/problems/sort-list/