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

示例 1：

**输入：**head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

**输入：**head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

**输入：**head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 10(4)] 内

-10(5) <= Node.val <= 10(5)

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

使用归并排序，空间复杂度为logn

先找中点，然后把链表分割，最后合并

分割时注意把链表切断即mid->next = nullptr

合并时可以新增一个虚节点减少判空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode *mid = head;
        ListNode *i = head->next;
        while (i != nullptr && i->next != nullptr) {
            i = i->next->next;
            mid = mid->next;
        }

        ListNode *rightHead = mid->next;
        mid->next = nullptr;

        ListNode *l = sortList(head);
        ListNode *r = sortList(rightHead);

        return merge(l, r);
    }
    ListNode *merge(ListNode *l, ListNode *r) {
        ListNode pre(-1);
        ListNode *cur = &pre;
        while (l != nullptr && r != nullptr) {
            if (l->val < r->val) {
                cur->next = l;
                l = l->next;
            } else {
                cur->next = r;
                r = r->next;
            }
            cur = cur->next;
        }
        if (l != nullptr)
            cur->next = l;
        else
            cur->next = r;
        return pre.next;
    }
};

想要常数级空间，我们可以手动分割

先求链表长度，然后每次设定一个子链表长度。按照此长度分割整个链表，最后合并。

链表长度翻倍后重复上述操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == nullptr)
            return nullptr;
        int len = 0;
        ListNode *index = head;
        while (index != nullptr) {
            index = index->next;
            len++;
        }
        ListNode dummy(-1, head);
        for (int subLen = 1; subLen < len; subLen <<= 1) {
            ListNode *pre = &dummy;
            ListNode *cur = dummy.next;

            while (cur) {
                ListNode *head1 = cur;

                for (int i = 1; i < subLen && cur->next != nullptr; i++)
                    cur = cur->next;

                ListNode *head2 = cur->next;
                cur->next = nullptr;
                cur = head2;
                for (int i = 1; i < subLen && cur != nullptr && cur->next != nullptr; i++)
                    cur = cur->next;

                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 *l, ListNode *r) {
        ListNode pre(-1);
        ListNode *cur = &pre;
        while (l != nullptr && r != nullptr) {
            if (l->val < r->val) {
                cur->next = l;
                l = l->next;
            } else {
                cur->next = r;
                r = r->next;
            }
            cur = cur->next;
        }
        if (l != nullptr)
            cur->next = l;
        else
            cur->next = r;
        return pre.next;
    }
};