44-排序链表

最优解法没做出来，插入排序前面做过了。

参考做法

使用归并排序，有两种方法：一种是自顶向下，另一种是自底向上。

如果要达到常数级空间复杂度，那么就需要使用自底向上的解法。

自顶向下

算法思想

递归地从中间拆分链表，然后进行排序，再合并两个有序链表。

找链表中间节点可以使用快慢指针，快指针走两步，慢指针走一步，当快指针到达末尾，慢指针指向链表中间节点。

设中间节点为mid，记下mid的下一个节点，然后将mid->next设为null。

分别排序前后两个链表，然后进行合并。

注意：有一种特殊情况就是：当链表有两个节点时，mid最终会指向第二个结点，会发生错误，因为递归排序前后两个链表时，前面链表还是原链表，后面链表是空。那么它会一直卡在两个节点的链表这里，陷入死循环。

所以本来递归地终止条件是当传入链表为空，或只有一个节点。

为了避免上述特殊情况，再加上一个条件就是当链表只有两个节点时：比较前后两个节点的值，升序，则直接返回；否则，交换两个节点，返回头节点。

算法实现

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sort(head);
    }

    ListNode * sort(ListNode * head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        //链表只有两个节点的特殊情况
        if(head->next->next == nullptr) {
            if(head->val < head->next->val) {
                return head;
            } else {
                ListNode * node = head->next;
                head->next = nullptr;
                node->next = head;
                return node;
            }
        }
        ListNode * slow = head;
        ListNode * fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode * mid = slow;
        ListNode * next_mid = mid->next;
        mid->next = nullptr;
        return merge(sortList(head), sortList(next_mid));

    }

    ListNode * merge(ListNode * l1, ListNode * l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;

        ListNode * dummy = new ListNode();
        ListNode * node = dummy, * node1 = l1, * node2 = l2;
        while (node1 != nullptr && node2 != nullptr) {
            if(node1->val < node2->val) {
                node->next = node1;
                node1 = node1->next;
            } else {
                node->next = node2;
                node2 = node2->next;
            }
            node = node->next;
        }
        if (node1 != nullptr) {
            node->next = node1;
        }
        if(node2 != nullptr) {
            node->next = node2;
        }
        return dummy->next;
    }


};

也可以在找中间节点的时候避免这种情况，就是将上述的while条件fast && fast->next改成fast->next && fast->next->next。然后删掉处理 链表只有两个节点的特殊情况的代码即可。

那么sort函数写成：

ListNode * sort(ListNode * head) {
    if(head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode * slow = head;
    ListNode * fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode * mid = slow;
    ListNode * next_mid = mid->next;
    mid->next = nullptr;
    return merge(sortList(head), sortList(next_mid));

}

性能分析

时间复杂度：$O(NlogN)$。

空间复杂度：递归栈存了$$logN$$个节点。时间复杂度为$O(logN)$。

自底向上

算法思想

首先求得链表的长度length。然后将链表拆分成子链表，进行合并。

1. 使用subLength代表每次需要排序的子链表的长度，初始subLength = 1
2. 每次将链表拆分成若干个长度为subLength的子链表(最后一个子链表有可能小于subLength，如果除不尽)按照每两个子链表一组进行合并，合并后可以得到若干个长度为 subLength * 2 的有序子链表(最后一个子链表长度有可能小于subLength * 2)。
3. 将subLength值加倍，重复第二步，直到subLength的值大于或等于length。

整个链表排序完成。

简单说就是：两个链表一组进行合并。初始每个链表长度为1，合并后是若干个长度为2的有序子链表；然后再两个一组，这时，每个子链表长度为2，合并后是若干个长度为4的有序子链表。一直合并下去，直到合并后的有序子链表长度大于等于链表总长度。

算法实现

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        int length = 0;
        ListNode * node = head;
        while (node) {
            length++;
            node = node->next;
        }
        ListNode * dummy = new ListNode(0);
        dummy->next = head;

        for(int subLength = 1; subLength < length; subLength *= 2) {
            //每次合并都从头开始
            ListNode * pre = dummy, * cur = dummy->next;
            while (cur != nullptr) {
                //确定待合并的第一个链表的头节点
                ListNode * head1 = cur;
                for (int i = 1; i < subLength && cur->next != nullptr; i++) {
                    cur = cur->next;
                }
                //待合并的第二个链表的头节点
                ListNode *head2 = cur->next;
                cur->next = nullptr;
                cur = head2;
                //head2有可能为空，所以这个循环要判断cur是否为空
                for (int i = 1; i < subLength && cur != nullptr && cur->next != nullptr; i++) {
                    cur = cur->next;
                }
                //记录下一组待合并链表的头节点，cur有可能为空，需要判断
                ListNode *next = nullptr;
                if (cur != nullptr) {
                    next = cur->next;
                    cur->next = nullptr;
                }
                ListNode *merged = merge(head1, head2);
                //连接有序子链表
                pre->next = merged;
                while (pre->next != nullptr) {
                    pre = pre->next;
                }
                //指向下一组待合并链表头节点
                cur = next;
            }
        }
        return dummy->next;
    }


    ListNode * merge(ListNode * l1, ListNode * l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;

        ListNode * dummy = new ListNode();
        ListNode * node = dummy, * node1 = l1, * node2 = l2;
        while (node1 != nullptr && node2 != nullptr) {
            if(node1->val < node2->val) {
                node->next = node1;
                node1 = node1->next;
            } else {
                node->next = node2;
                node2 = node2->next;
            }
            node = node->next;
        }
        if (node1 != nullptr) {
            node->next = node1;
        }
        if(node2 != nullptr) {
            node->next = node2;
        }
        return dummy->next;
    }


};

性能分析

时间复杂度：$O(NlogN)$。

空间复杂度：$O(1)$。