XTAO's Tech Blog
0%

[Leetcode]148. Sort List(C++)

发表于 更新于 分类于 ， 评论数：
1.5k 1 分钟

题目描述

题目链接：148. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

例子

例子 1

Input: head = [4,2,1,3]
Output: [1,2,3,4]

例子 2

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

例子 3

Input: head = []
Output: []

Follow Up

  • Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Constraints

  • The number of nodes in the list is in the range [0, 5 * 10^4].
  • -10^5 <= Node.val <= 10^5

解题思路

题目要求在 O(nlogn) 的时间复杂度下对链表排序，不难想到可以使用归并排序，由于是链表所以可以自由控制节点的位置，无需使用额外空间。归并算法的思路是对链表首先分半，对前后两半递归使用排序，将排好序的链表合并在一起就行。合并排好序的链表很简单，可以参考：[Leetcode]21. Merge Two Sorted Lists(C++)

代码如下：

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
class Solution {
public:
    ListNode* sortList(ListNode* head) {

        // for linked list with length of 0 or 1, no need to sort
        if (!head || !head->next) {
            return head;
        }

        ListNode *dummy = new ListNode();
        dummy->next = head;

        ListNode *fast = dummy;
        ListNode *slow = dummy;

        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        fast = slow->next;
        slow->next = nullptr;

        return merge(sortList(head), sortList(fast));
    }

private:
    ListNode* merge(ListNode *A, ListNode *B) {
        ListNode *dummy = new ListNode();
        ListNode *curr = dummy;

        while (A && B) {
            if (A->val <= B->val) {
                curr->next = A;
                A = A->next;
            } else {
                curr->next = B;
                B = B->next;
            }
            curr = curr->next;
        }

        if (!A) {
            curr->next = B;
        }
        if (!B) {
            curr->next = A;
        }

        return dummy->next;
    }
};
  • 时间复杂度: O(nlgn)
  • 空间复杂度: O(1)

GitHub 代码同步地址： 148.SortList.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章