链表排序

1. 插入排序

• 只要注意每次判断比前面的大那就不需要回头
• 否则需要从头找合适的位置

ListNode* insertSort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode dummy; dummy.next = head;
    ListNode* prev = head;
    ListNode* curr = head->next;
    while (curr) {
        if (prev->val <= curr->val) {
            prev = curr;
            curr = curr->next;
        } else {
            ListNode* t = &dummy;
            while (t->next && t->next->val <= curr->val) t = t->next;
            prev->next = curr->next;
            curr->next = t->next;
            t->next = curr;
            curr = prev->next;
        }
    }
    return dummy.next;
}

2. 归并排序

• 不论是主递归还是merge都要求两个链表以nullptr结尾
• 也就是在合适的地方断开

2.1 递归版本

ListNode* mergeTwoList(ListNode* p2a, ListNode* p2b) {
    ListNode dummy;
    ListNode* ptr = &dummy;
    while (p2a || p2b) {
        int a = p2a ? p2a->val : INT_MAX;
        int b = p2b ? p2b->val : INT_MAX;
        if (a < b) {
            ptr->next = p2a;
            p2a = p2a->next;
        }
        else {
            ptr->next = p2b;
            p2b = p2b->next;
        }
        ptr = ptr->next; // 别忘了
    }
    return dummy.next;
}

ListNode* mergeSort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* slow = head, *fast = head;
    while (fast) { // 链表快慢指针有多种形式，要会灵活运用
        fast = fast->next;
        if(fast) fast = fast->next;
        if(fast) slow = slow->next; // if(fast)：slow指向第一个链表的最后一位结点
    }
    ListNode* head2 = slow->next;
    slow->next = nullptr;
    return mergeTwoList(mergeSort(head), mergeSort(head2));
}

2.2 非递归版本

ListNode* mergeTwoList(ListNode* p2a, ListNode* p2b) {
    ListNode dummy;
    ListNode* ptr = &dummy;
    while (p2a || p2b) {
        int a = p2a ? p2a->val : INT_MAX;
        int b = p2b ? p2b->val : INT_MAX;
        if (a < b) {
            ptr->next = p2a;
            p2a = p2a->next;
        }
        else {
            ptr->next = p2b;
            p2b = p2b->next;
        }
        ptr = ptr->next; // 别忘了
    }
    return dummy.next;
}

ListNode* mergeSort(ListNode* head) {
    if (!head || !head->next) return head;
    int n = 0;
    ListNode* ptr = head;
    while (ptr) { // 统计链表长度
        ++n;
        ptr = ptr->next;
    }
    ListNode dummy;
    dummy.next = head;
    ptr = &dummy;
    ListNode* prev, *l, *r, *t, *next; // 屮，5个指针
    for (int w = 1; w < n; w <<= 1) {
        prev = &dummy;
        l = dummy.next;
        r = nullptr;
        while (l) {
            // 第一个子链表的最后一个元素 注意：i从1开始
            t = l;
            for (int i = 1; i < w && t; ++i) t = t->next;
            r = nullptr;
            if (t) {
                r = t->next;
                t->next = nullptr;
            }
            // 第二个子链表的最后一个元素 注意：i从1开始
            t = r;
            for (int i = 1; i < w && t; ++i) t = t->next;
            next = nullptr;
            if (t) {
                next = t->next;
                t->next = nullptr;
            }
            // 合并子链表
            ListNode* ret = mergeTwoList(l, r);
            prev->next = ret;
            // prev指向合并后的子链表的最后一个元素
            while (prev->next) prev = prev->next;
            l = next;
        }
    }
    return dummy.next;
}

3. 快速排序

• 其实对于链表，由于不需要额外空间，归并排序其实很优秀了；快速排序由于需要选取pivot，选的不好，会变成n^2，而归并排序是稳定的nlogn
• pivot的选取可以将中点节点移到链头充当pivot或者随机一个节点充当pivot，否则对于有序数列，会退化为n^2
• 由于无法采用l和r两边向中间靠拢的方式划分集合，只能采用单边形式，所以遇到“窄数据”或者都是一样值（窄特例化），也会退化为n^2

ListNode* quickSort(ListNode* head) {
    if (!head || !head->next) return head;
    int pivot = head->val;
    ListNode L, R;
    ListNode* l = &L, *r = &R;
    ListNode* ptr = head->next;
    while (ptr) {
        if (ptr->val <= pivot) {
            l->next = ptr;
            l = l->next;
        }
        else {
            r->next = ptr;
            r = r->next;
        }
        ptr = ptr->next;
    }
    l->next = nullptr; // 断尾
    r->next = nullptr; // 断尾
    l = quickSort(L.next);
    r = quickSort(R.next);
    head->next = r;
    if (!l) return head;
    ListNode* t = l;
    while (t->next) t = t->next;
    t->next = head;
    return l;
}

• 取中间作为pivot

ListNode* quickSort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* slow = head, *fast = head;
    while (fast) {
        fast = fast->next;
        if (fast) fast = fast->next;
        if (fast) slow = slow->next;
    }
    ListNode* newHead = slow->next;
    slow->next = newHead->next;
    newHead->next = head;

    int pivot = newHead->val;
    ListNode L, R;
    ListNode* l = &L, *r = &R;
    ListNode* ptr = newHead->next;
    while (ptr) {
        if (ptr->val <= pivot) {
            l->next = ptr;
            l = l->next;
        }
        else {
            r->next = ptr;
            r = r->next;
        }
        ptr = ptr->next;
    }
    l->next = nullptr; // 断尾
    r->next = nullptr; // 断尾
    l = quickSort(L.next);
    r = quickSort(R.next);
    newHead->next = r;
    if (!l) return newHead;
    ListNode* t = l;
    while (t->next) t = t->next;
    t->next = newHead;
    return l;
}

4. 辅助代码

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int _v = 0) :val(_v), next(nullptr) {}
};

ListNode* genList(int n, int range) { // 数目， 分布范围
    ListNode dummy;
    ListNode* ptr = &dummy;
    for (int i = 0; i < n; ++i) {
        int r = rand() % range;
        ListNode* tmp = new ListNode(r);
        ptr->next = tmp;
        ptr = ptr->next;
    }
    return dummy.next;
}

void parseList(ListNode* p, bool show=true) {
    int ret = 0;
    int cnt = 0;
    while (p) {
        if(show) cout << p->val << "\t";
        p = p->next;
        ++cnt;
        if (show && cnt / 10) {
            ret += cnt;
            cnt = 0;
            cout << endl;
        }
    }
    ret += cnt;
    cout << "总计:"<< ret << endl;
}

int main() {
    ListNode* ptr = genList(1000, 1000);
    parseList(ptr, true);
    // ptr = yourSort(ptr);
    parseList(ptr, true);
    return 0;
}