题目描述

题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度，时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n2），其中最适合链表的排序算法是归并排序

法一 自顶向下归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head){
		return sortList(head, nullptr);
	}
	
	ListNode* sortList(ListNode* head, ListNode* tail){
		if(head==nullptr){
			return head;
		}
		if(head->next==tail){
			head->next=nullptr;
			return head;
		}
		ListNode *fast=head, *slow = head;
		while(fast!=tail){
			slow = slow->next;
			fast = fast->next;
			if(fast!=tail){
				fast = fast->next;
			}
		}
		ListNode* mid = slow;
		return merge(sortList(head, mid), sortList(mid, tail));
	}
	
	ListNode* merge(ListNode *l1, ListNode *l2){
		ListNode *dummy = new ListNode(-1);
		ListNode *cur=dummy, *s1=l1, *s2=l2;
		while(s1 && s2){
			if(s1->val < s2->val){
				cur->next = s1;
				s1 = s1->next;
			} else {
				cur->next = s2;
				s2 = s2->next;
			}
			cur = cur->next;
		}
		cur->next = s1 ? s1 : s2;
		return dummy->next; 
	}
};

法二）自底向上归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }
        ListNode* dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode* prev = dummyHead, *curr = dummyHead->next;
            while (curr != nullptr) {
                ListNode* head1 = curr;
                for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* head2 = curr->next;
                curr->next = nullptr;
                curr = head2;
                for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* next = nullptr;
                if (curr != nullptr) {
                    next = curr->next;
                    curr->next = nullptr;
                }
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                curr = next;
            }
        }
        return dummyHead->next;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};