LeetCode HOT100 - 排序链表

不会，这种平时不做的数据结构确实是弱项啊

题解参考：https://leetcode.cn/problems/sort-list/solutions/13728/sort-list-gui-bing-pai-xu-lian-biao-by-jyd

时间复杂度 O(nlogn) 想到二分，进而想到归并排序

归并排序就是每次分成两部分，两部分各自排序，接着合并两部分

正常这样的操作就是使用递归，如下所示

实现点就在于使用快慢指针找到链表的中点，从中点断开链表

递归的终止条件自然就是只有一个节点或者空节点

合并阶段是将两个排序链表合并

建一个辅助节点作为头部，接着两个指针分别遍历 left 和 head ，从小到大加入到辅助节点中

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !(head->next)) {
            return head;
        }
        auto slow = head, fast = head->next;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        auto mid = slow->next;
        slow->next = nullptr;
        auto left = sortList(head), right = sortList(mid);
        ListNode *tmp = new ListNode();
        auto res = tmp;
        while (left && right) {
            if (left->val < right->val) {
                tmp->next = left;
                left = left->next;
            } else {
                tmp->next = right;
                right = right->next;
            }
            tmp = tmp->next;
        }
        tmp->next = left ? left : right;
        return res->next;
    }
};

但是递归的空间不是 O(1)

所以如果要满足要求的话需要使用迭代的方式来实现

就是自底向上

一开始将每个节点看作是单独的节点，每轮相邻的比较合并形成更大的子链表

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        auto tmp = head;
        int length = 0, intv = 1;
        while (tmp) {
            tmp = tmp->next;
            length++;
        }
        auto res = new ListNode();
        res->next = head;
        while (intv < length) {
            auto pre = res, tmp = res->next;
            while (tmp) {
                auto h1 = tmp;
                auto i = intv;
                while (i && tmp) {
                    tmp = tmp->next;
                    i--;
                }
                if (i) {
                    break;
                }
                auto h2 = tmp;
                i = intv;
                while (i && tmp) {
                    tmp = tmp->next;
                    i--;
                }
                auto c1 = intv, c2 = intv - i;
                while (c1 && c2) {
                    if (h1->val < h2->val) {
                        pre->next = h1;
                        h1 = h1->next;
                        c1--;
                    } else {
                        pre->next = h2;
                        h2 = h2->next;
                        c2--;
                    }
                    pre = pre->next;
                }
                pre->next = c1 ? h1 : h2;
                while (c1 > 0 || c2 > 0) {
                    pre = pre->next;
                    c1--;
                    c2--;
                }
                pre->next = tmp;
            }
            intv *= 2;
        }
        return res->next;
    }
};