链表 – 排序链表

Leetcode link : 排序链表

1 插入排序 O(n^2)

插入排序的原理是在数组前端维护一个有序的子数组，待排序元素通过查询子数组的合适的位置进行插入。

故实际上维护了两个数组，放到链表中需要维护两个链表。

• 1 cur指向原数组
• 2 in_cur指向有序的子数组（新创建）

实际排序步骤：

• 1 使用原数组进行循环
• 2 从有序链表中找到待排序元素插入位置的前一个位置
• 3 将待排序元素插入有序链表（模拟中间插入过程）

实际代码如下：

/**
 * 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) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = head;
        while(cur){
            ListNode* in_cur = dummy;
            ListNode* next_node = cur->next;
            // 1 寻找到有序链表中待插入的位置的前一个位置
            while(in_cur->next && in_cur->next->val <= cur->val){
                in_cur = in_cur->next;
            }

            // 2 将待排序的元素插入有序链表（模拟中间插入过程）
            // in_cur=dummy ; 4->nullptr
            cur->next = in_cur->next;
            // dummy -> 4 -> nullptr
            in_cur->next = cur;

            // 3 cur从原数组中获取下一个待排序元素
            cur = next_node;
        }
        return dummy->next;
    }
};

2 容器排序

构建一个<int, ListNode*>的容器，使用容器对int进行排序，然后重建有序链表。

Note：需要将容器中排序后的最后一个元素的next设置为nullptr;

具体代码如下：

/**
 * 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) {
        vector<pair<int, ListNode*>> vec;
        // 1 填入vector
        ListNode* cur = head;
        while(cur){
            vec.push_back({cur->val, cur});
            cur = cur->next;
        }
        // 2 vector排序
        sort(vec.begin(), vec.end(), [](pair<int, ListNode*>& a, pair<int, ListNode*>& b) {return a.first<b.first;});
        // 3 重建链表
        ListNode* dummy = new ListNode(0);
        ListNode* in_cur = dummy;
        for(int i=0; i<vec.size(); i++){ // Note：最后一个元素的尾部需要置空 if (i==vec.size()-1) vec[i].second->next=nullptr;
            in_cur->next = vec[i].second;
            in_cur = in_cur->next;
        }
        return dummy->next;
    }
};