[Leetcode] 第148题排序链表

一、题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

二、题目分析

1）采用快排的思想，以第一个节点为基准，分成左右两部分分别排序

2）因为是链表，所以用一个整数cnt来标记要进行排序的链表节点的个数，不能超过这个数目

三、代码实现

 1 class Solution {
 2 public:
 3     ListNode* sortList(ListNode* head) {
 4         int cnt = 0;
 5         ListNode *p = head;
 6         while (p) {
 7             ++cnt;
 8             p = p->next;
 9         }
10         return quickSort(head, cnt);
11     }
12 private:
13     ListNode* quickSort(ListNode *head, int cnt) {
14         //cnt记录要进行排序的节点个数
15         if (!head || !head->next || cnt == 0 || cnt == 1)
16             return head;
17         int left_cnt = 0, right_cnt = 0, base = head->val;
18         ListNode* cur = head->next, *pre = head, *p = head;
19         for (int i = 1; i < cnt; ++i) {
20             if (cur&&cur->val < base) {
21                 ++left_cnt;
22                 pre->next = cur->next;
23                 cur->next = head;
24                 head = cur;
25                 cur = pre->next;
26             }
27             else if (cur&&cur->val >= base) {
28                 ++right_cnt;
29                 pre = cur;
30                 cur = cur->next;
31             }
32         }
33         ListNode* left_node = quickSort(head, left_cnt);
34         ListNode* right_node = quickSort(p->next, right_cnt);
35         p->next = right_node;
36         head = left_node;
37         return head;
38     }
39 };

[Leetcode] 第148题 排序链表

[Leetcode] 第148题排序链表