LeetCode 148. Sort List（链表排序，Medium）

叁歲伎倆 2022-04-24 09:26 141阅读 0赞

# LeetCode 148. Sort List （Medium） #

难度 : Medium

## 1、题目描述 ##

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

排序一个链表，要求以 O(n log n) 的时间复杂度和常数级的空间复杂度。

例1 :

Input: 4->2->1->3
    Output: 1->2->3->4

例2 :

Input: -1->5->3->4->0
    Output: -1->0->3->4->5

## 2、分析 ##

### 思考过程： ###

首先，看到题目排序且时间复杂度为 O(n log n)，想到时间复杂度为 O(n log n) 的算法有归并排序，快速排序，堆排序。链表的链式结构不太容易抽象成堆，所以堆排序不合适。继续考虑归并和快拍。虽然归并排序在 merge 的时候需要开辟一个和原数组一样大小的空间（即 O(n) 的空间复杂度）用于将合并后的有序数组拷贝到原数组，但是对于链表的归并排序，可以直接在原链表的基础上对链表进行拆分合并，无需开辟新的链表。快排也是可以的，只不过没有改变链表节点的顺序，只是改变了节点里面的值

## 3、解法一： 归并排序、 ##

### 解决步骤 ###

根据归并排序的思想，递归的对链表进行查分，拆分的时候是以链表的中点为界限进行划分的，然后合并，在合并的时候进行外部排序。所以：

1.  找链表的中点（快慢指针赛跑）。
2.  以中点为界限，拆分链表。
3.  合并拆分后的链表。

注意：在找中点的时候，当链表有偶数个节点时，我们找到中间两个节点中左边的那一个，因为头结点到 middle 为左半部分，middle->next 到链表结尾为有半部分。如果找的中点是中间两个节点的右边那一个，则无法确定左半部分的结束，并且当链表的节点只剩两个时，将无法划分下去。

### 代码 ###

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next){
                return head;
            }
            
            ListNode* right = sortList(slow->next);
            slow->next = NULL;
            ListNode* left = sortList(head);
            return mergeTwoLists(left, right);
        }
        
        ListNode* findMiddleNode(ListNode* head){
            //快慢指针赛跑法找中点
            ListNode* fast = head;
            ListNode* slow = head;
            while(fast && fast->next){
                fast = fast->next;
                if(fast->next){ //限制当有偶数个节点时，中点为中间两个的左边那一个。
                    fast = fast->next;
                    slow = slow->next;
                }
            }
        }
        
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
            if(!l1){
                return l2;
            }
            if(!l2){
                return l1;
            }
            if(l1->val < l2->val){
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }else{
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }
        }
    };

## 4、解法二：快速排序 ##

在进行 partion 划分的时候，可以以开始节点的 val 为参考值。用两个指针p1、p2，使得 p1 及其之前 \[begin, p1\] 的值都小于参考值，p1 到 p2 之间 (p1 p2\] 的值都大于参考值。得到划分的节点位置后，再递归的对该划分节点左右两侧进行划分。

1.  p1 只想 begin 位置，p2 指向 begin 的 next位置，开始遍历
2.  当 p2 位置的值大于参考值时，p2 往 next 方向移动一位，否则交换 p1->next 与 p2 的 val，然后p1、p2都往 next 方向移动一位
3.  知道 p2 指向 end 位置结束遍历
4.  结束遍历后，交换 begin 和 p1 的 val，返回 p1 节点。

### 代码如下： ###

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next){
                return head;
            }
            ListNode* end = head;
            while(end->next){
                end = end->next;        
            }
            quickSort(head, NULL);
            return head;
        }
        void quickSort(ListNode* begin, ListNode* end){
            if(begin != end){
                ListNode* index = partion(begin, end);
                quickSort(begin, index);
                quickSort(index->next, end);
            }
        }
        
        ListNode* partion(ListNode* begin, ListNode* end){
            ListNode* p1 = begin;
            ListNode* p2 = p1->next;
            while(p2 != end){
                if(p2->val > begin->val){
                    p2 = p2->next;
                }else{
                    swap(p1->next->val, p2->val);
                    p1 = p1->next;
                    p2 = p2->next;
                }
            }
            swap(begin->val, p1->val);
            return p1;
        }
    };

## 5、本题考点 ##

这是一道综合性题目。涉及到 对几种排序的理解，还有链表找中点，合并两个有序链表。

链表找中点在 2019 年春招中被小米面试官问到，如何一次遍历就找到链表的中点。快慢指针赛跑法解决

合并两个有序链表为 LeetCode 21. Merge Two Sorted Lists。难度 easy。上边代码用的是递归的方式合并的，非递实现如下：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode* head = new ListNode(0); //头插法
            ListNode* result = head;
            while(l1 && l2){
                if(l1->val < l2->val){
                    head->next = l1;
                    l1 = l1->next;
                }else{
                    head->next = l2;
                    l2 = l2->next;
                }
                head = head->next;
            }
            if(l1){
                head->next = l1;
            }
            if(l2){
                head->next = l2;
            }
            return result->next;
        }
    };