【LeetCode】148. 排序链表

题目描述

这道题目来自 LeetCode 148. 排序链表。

题目描述如下：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

输入输出示例与数据范围

思路

实际上这道题的正确解法是链表的归并排序，但是我自己反复写了很多次，对$O(n\log n)$的解法仍然不是很熟练，遂在博客中对完整的链表归并排序进行一次整理。

归并排序的思想是分治，因此首先要做的是将排序问题分解为若干个不可再分的原子性子问题，对于链表排序问题，不可再分的子问题恰好是链表中只有一个结点的情况。

因此，首先，我们不断递归地对链表进行分治处理，采用左闭右开的方式$[\text{head},\text{tail})$，当 head 为空或 head -> next == tail 时，表明问题分解达到边界：

• 如果 head == nullptr，证明整个链表就是一个空链表；
• 如果 head -> next == nullptr，说明当前子问题的链表只包含一个结点，我们不需要对只包含一个结点的链表进行排序，此时直接返回。

达到边界返回后，我们处理的是包含大于一个结点的子问题，针对每一个子问题，我们要做的是将这个链表从中间分成两部分，也就是形成两个子链表，并将子链表合并为有序链表。

C++ 实现

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 归并排序
        return mergeSort(head, nullptr);
    }
    ListNode* mergeSort(ListNode *head, ListNode *tail) {
        if(head == nullptr) return nullptr;
        if(head -> next == tail) {
            head -> next = nullptr;
            return head;
        }
        ListNode *slow = head, *fast = head;
        do {
            slow = slow -> next;
            fast = fast -> next;
            if(fast != tail) fast = fast -> next;
        } while(fast != tail);

        return merge(mergeSort(head, slow), mergeSort(slow, tail));
    }

    ListNode* merge(ListNode *l1, ListNode *l2) {
        ListNode *dummyNode = new ListNode(0);
        ListNode *t = dummyNode, *p = l1, *q = l2;
        while(p && q) {
            if(p -> val < q -> val) {
                t -> next = p;
                p = p -> next;
            } else {
                t -> next = q;
                q = q -> next;
            }
            t = t -> next;
        }
        if(p) {
            t -> next = p;
        }
        if(q) {
            t -> next = q;
        }
        t = dummyNode -> next;
        delete dummyNode;
        return t;
    }
};