题目

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

示例 1:

1
2


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

示例 2:

1
2


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

题解

这道题要求时间复杂度为O(nlogn)，常用的时间复杂度为O(nlogn)的排序算法有快排、堆排、归并排序。

从快排和堆排的实现逻辑来看，它们要对元素进行交换，而这些操作在链表中并不好操作，一个折衷的方法是将链表的结点放到一个数组中，对数组进行快排或归并排序，但这样的话，空间复杂度就上去了。

而归并排序基于合并，没有交换操作，可直接在链表基础上进行操作，因此应该是使用归并排序的。

为了温习快排和堆排的实现，自己依旧实现了一遍快排和堆排，对应的代码如下：

 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83


void quick_sort(vector<ListNode*> &v, int l, int r) {
    int left = l;
    int right = r;

    if (left >= right)return;
    ListNode* data = v[left];
    while (left < right) {
        while (left < right && v[right]->val > data->val)
            right--;
        
        if(left < right)
            v[left++] = v[right];
        
        while (left < right && v[left]->val < data->val)
            left++;

        if(left < right)
            v[right--] = v[left];
    }

    quick_sort(v, l, left - 1);
    quick_sort(v, left + 1, r);

    v[left] = data;
}

void adjust(vector<ListNode*> &v, int index, int count) {
    if (count <= 0) return;

    for (int node = index * 2 + 1; node < count; node = node * 2 + 1) {
        
        if (node + 1 < count && v[node + 1]->val > v[node]->val)
            node++;

        if (v[node]->val < v[index]->val) {
            break;
        }

        ListNode* tmp = v[index];
        v[index] = v[node];
        v[node] = tmp;
        index = node;
    }
}

void heap_sort(vector<ListNode*> &v) {
    if (v.empty())return;

    for (int i = v.size() / 2 - 1; i >= 0; i--) {
        adjust(v, i, v.size());
    }
    
    for (int i = v.size() - 1; i >= 0; i--) {
        ListNode* tmp = v[0];
        v[0] = v[i];
        v[i] = tmp;

        adjust(v, 0, i);
    }
}

ListNode* sortList(ListNode* head) {
   if (!head) return nullptr;
   vector<ListNode*> v;
   for (auto node = head;node != nullptr;node = node->next) {
       v.push_back(node);
   }

   // 这里可选快排或是堆排
   //quick_sort(v, 0, v.size() - 1);
   heap_sort(v);

   for (int i = 0; i < v.size();i++) {
       if (i + 1 < v.size()) {
           v[i]->next = v[i + 1];
       }
       else {
           v[i]->next = nullptr;
       }
   }

   return v[0];
}

归并排序的实现自己也已经忘记了，于是温习了一下相关的原理，之后开始实现，但最开始的实现有问题，自己没有想到好的对链表进行二分的办法（实际上自己傻逼了，忘记了快慢指针），所以是按照迭代的方式来的，导致时间复杂度较高，运行结果超时，对应的代码如下：

 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


ListNode* merge_list(ListNode* first, ListNode* second) {
    if (first == nullptr)return second;
    if (second == nullptr)return first;

    ListNode* i = first;
    ListNode* j = second;
    ListNode tmp(0);
    ListNode* head = &tmp;
    while (i != nullptr && j != nullptr) {
        if (i->val < j->val) {
            head->next = i;
            i = i->next;
        }
        else {
            head->next = j;
            j = j->next;
        }
        
        head = head->next;
    }

    head->next = i == nullptr ? j : i;
    return tmp.next;
}

ListNode* sortList(ListNode* head) {
   if (head == nullptr)return nullptr;

   ListNode* second = head->next;
   head->next = nullptr;

   ListNode* s = sortList(second);
   return merge_list(head, s);
}

后面参考讨论，使用快慢指针的方式对代码进行了优化，优化后的sortList函数如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


ListNode* sortList(ListNode* head) {
   if (!head || !head->next) return head;

   /// 快慢指针
   ListNode* slow = head;
   ListNode* fast = head->next;
   while (fast && fast->next) {
       slow = slow->next;
       fast = fast->next->next;
   }

   ListNode* tmp = slow->next;
   slow->next = nullptr;

   ListNode* s = sortList(head);
   ListNode* f = sortList(tmp);
   return merge_list(s, f);
}

这样再运行后就没有问题，但空间复杂度已经达不到O(1）的要求，因此还要对代码进行优化，参考讨论，需要使用迭代的方式对链表进行归并排序。大体的原理是这样的，首先我们将链表分成长度为1的子链表表，然后对两两的对这些链表进行归并，这样我们就得到了长度为2且有序的链表。之后我们继续对这些长度为2的链表两两进行归并，进而得到长度为4的链表，重复这个过程，直到所有的链表合并成要给链表。

对应的代码如下：

 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


ListNode* cut(ListNode* head, int size) {
    while (--size && head) head = head->next;
    
    if (!head)return nullptr;

    ListNode* tmp = head->next;
    head->next = nullptr;
    return tmp;
}

ListNode* sortList(ListNode* head) {
    ListNode dummy_head(0);
    dummy_head.next = head;
    ListNode* tmp = head;
    int len = 0;
    while (tmp != nullptr) {
        tmp = tmp->next;
        len++;
    }

    for (int size = 1; size < len; size *= 2) {
        ListNode* curr = dummy_head.next;
        auto tail = &dummy_head;

        while (curr) {
            /// 将链表裁剪为长度为size大小的子链表，并进行归并
            ListNode* left = curr;
            ListNode* right = cut(left, size);
            curr = cut(right, size);
            tail->next = merge_list(left, right);

            while (tail->next) {
                tail = tail->next;
            }
        }
    }

    return dummy_head.next;
}

题目

题解

参考链接：