148 排序链表

本文最后更新于：2022年4月9日 中午

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

进阶：

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

Solution

  • 插入排序，参考 [147 对链表进行插入排序]，超时
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
// @lc code=start
/**
 * 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;
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* pre = dummyHead->next;

        while(pre->next){
            int val = pre->next->val;
            ListNode* nex = pre->next->next;
            ListNode* pi = dummyHead;
            for(; pi!=pre; pi=pi->next){
                if(pi->next->val > val){
                    ListNode* pj = pi->next;
                    ListNode* swapNode = pre->next;

                    pi->next = swapNode;
                    swapNode->next = pj;
                    pre->next = nex;
                    break;
                }
            }
            if(pi==pre) pre = pre->next;
        }
        return dummyHead->next;
    }
};
// @lc code=end

参考 LeetCode官方

  • 归并排序（自顶向下）
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
// @lc code=start
/**
 * 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){
        return sortList(head, nullptr);
    }
    ListNode* sortList(ListNode* head, ListNode* tail) {
        if(!head) return head;
        if(head->next == tail){
            head->next = nullptr;
            return head;
        }

        // find mid
        ListNode* slow=head, *fast=head;
        while(fast != tail){
            slow = slow->next;
            fast = fast->next;
            if(fast != tail)
                fast = fast->next;
        }
        ListNode* mid = slow;
        return merge(sortList(head, mid), sortList(mid, tail));
    }

    ListNode* merge(ListNode* l1, ListNode* l2){
        ListNode* dummyHead = new ListNode(0);
        ListNode* cur = dummyHead;
        while(l1 && l2){
            if(l1->val <l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1)
            cur->next = l1;
        if(l2)
            cur->next = l2;

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！