(高频考题)148. 排序链表(归并排序)

阳光穿透心脏的1/2处 2022-12-10 03:44 197阅读 0赞

题目要求时间空间复杂度分别为O(nlogn)O(nlogn)和O(1)O(1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序；

对数组做归并排序的空间复杂度为 O(n)O(n)，分别由新开辟数组O(n)O(n)和递归函数调用O(logn)O(logn)组成，而根据链表特性：

数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；  
递归额外空间：递归调用函数将带来O(logn)O(logn)的空间复杂度，因此若希望达到O(1)O(1)空间复杂度，则不能使用递归。  
通过递归实现链表归并排序，有以下两个环节：

分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；  
我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。  
找到中点 slow 后，执行 slow.next = None 将链表切断。  
递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。  
cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。  
合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。  
双指针法合并，建立辅助ListNode h 作为头部。  
设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。  
返回辅助ListNode h 作为头部的下个节点 h.next。  
时间复杂度 O(l + r)，l, r 分别代表两个链表长度。  
当题目输入的 head == None 时，直接返回None。

![Picture2.png][]

代码:

class Solution {
    public:
        ListNode* findMin(ListNode* head){
            ListNode* temp = NULL;
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast != nullptr && fast->next != nullptr){
                 temp = slow;
                 slow = slow->next;
                 fast = fast->next->next;
            }  
            temp->next = nullptr;  //切断链表
            return slow;   //返回中点
        }
    
         ListNode* merge(ListNode* l,ListNode* r){
               if(l == nullptr) return r;
               if(r == nullptr) return l;
               if(l->val < r->val){
                    l->next = merge(l->next,r);
                    return l;
               }else{
                    r->next = merge(l,r->next);
                    return r;
               }
        }
        ListNode* mergeSort(ListNode* head){  
            if(head->next == nullptr) return head;
            ListNode* mid = findMin(head);  //切断是切断中点以前
            ListNode* l = mergeSort(head);
            ListNode* r = mergeSort(mid);
            return merge(l,r);  //合并链表
        }
    
        
        ListNode* sortList(ListNode* head) {
            if(head == nullptr) return head;
            else return mergeSort(head);
        }
    };

[Picture2.png]: /images/20221123/5d84f8f2d95b44cba3b87014c9c9763b.png