【LeetCode热题100】【链表】排序链表

题目链接：148. 排序链表 - 力扣（LeetCode）

要排序一个链表，最快的方法是用一个数组将链表节点的值存起来然后排序数组后重新构建链表

但是从面试的角度，我们应该在链表原地排序，这里使用最简单的归并排序

归并排序分三步：拆成两个部分、继续归并排序两个部分、合并两个部分

拆成两个部分，要保持logn的递归树深度，每次拆分需要拆成两半差不多大小的，也就是寻找链表的中间节点，然后以中间节点为界限分成两个链表，即寻找链表的中间节点：使用快慢指针，当快指针到达链表末尾，慢指针即到达链表中间

    ListNode *findMidst(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

然后是考察合并两个有序链表：如果其中一个链表为空，则返回另一个链表，比较两个链表首节点的大小，让小的节点成为新链表的头节点，递归合并后面的

    ListNode *merge(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr)return l2;
        if (l2 == nullptr)return l1;
        if (l1->val < l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        }
        l2->next = merge(l1, l2->next);
        return l2;
    }

 最后是归并排序链表，先找出链表的中间位置拆分成两个链表，递归归并排序两个链表后合并

    ListNode *sortList(ListNode *left) {
        if (left == nullptr || left->next == nullptr)return left;
        ListNode *midst = findMidst(left);
        ListNode *right = midst->next;
        midst->next = nullptr;
        return merge(sortList(left), sortList(right));
    }

完整代码 

class Solution {
public:
    ListNode *merge(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr)return l2;
        if (l2 == nullptr)return l1;
        if (l1->val < l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        }
        l2->next = merge(l1, l2->next);
        return l2;
    }
 
    ListNode *findMidst(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
 
    ListNode *sortList(ListNode *left) {
        if (left == nullptr || left->next == nullptr)return left;
        ListNode *midst = findMidst(left);
        ListNode *right = midst->next;
        midst->next = nullptr;
        return merge(sortList(left), sortList(right));
    }
};