题目描述

blablabla

还有 交换链表节点的 待补
看了 yxc 已补 自己写的 其实没有mid这个 一直wa 最后看了视频想了回 一样大的 应该插中间 直接放后面导致链表没有拍对

样例

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode* get_tail(ListNode* head) {
        while(head->next != NULL) head = head->next;
        return head;
    }

    ListNode* quickSortList(ListNode* head) {
        // QuiSort(headm NULL); return head; // 交换val的
        // 归并排序 也是交换val;
        // return ListMergeSort(head);

        if(head == NULL) return head;

        ListNode* left = new ListNode(-1);
        ListNode* mid = new ListNode(-1);
        ListNode* right = new ListNode(-1);
        ListNode* ltail = left;
        ListNode* mtail = mid;
        ListNode* rtail = right;

        int k = head->val;
        for(ListNode* p = head; p != NULL; p = p->next) {
            if(p->val < k) ltail->next = p, ltail = ltail->next;
            else if(p->val == k) mtail->next = p, mtail = mtail->next;
            else rtail->next = p, rtail = rtail->next;
        }

        ltail->next = NULL, mtail->next = NULL, rtail->next = NULL;

        left->next = quickSortList(left->next);
        right->next = quickSortList(right->next);

        get_tail(left)->next = mid->next;
        get_tail(left)->next = right->next;
        return left->next;
    }



    void QuickSort(ListNode* l, ListNode* r) {
        if (l == r) return;
        // printf("%d %d\n", l?l->val:0, r?r->val:0);
        ListNode* cur = l; 
        int key = l->val;
        ListNode* p = l->next;
        while(p != r) {
            if (p->val < key) {
                cur = cur->next; 
                swap(p->val, cur->val);
            }
            p = p->next;
        }
        swap(l->val, cur->val);
        QuickSort(l, cur);
        QuickSort(cur->next, r);
    }

    ListNode* ListMergeSort(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* pFast = head;
        ListNode* pSlow = head;
        // 中间节点，快慢指针
        while (pFast != NULL && pFast->next == NULL) {
            pFast = pFast->next->next;
            pSlow = pSlow->next;
        }
        pFast = pSlow;
        pSlow = pSlow->next; 
        pFast->next = NULL;// 分割成2段
        head = ListMergeSort(head);
        pSlow = ListMergeSort(pSlow);
        head = merge(head, pSlow);
        return head;
    };

    ListNode* merge(ListNode* p1, ListNode* p2) {
        if (p1 == NULL || p2 == NULL) {
            return p1 == NULL ? p2 : p1;
        }
        // 找出合并后的链表头
        ListNode* head = NULL;
        if (p1->val > p2->val) {
            head = p2;
            p2 = p2->next;
        } else {
            head = p1;
            p1 = p1->next;
        }
        // 将2个链表中值较小的节点依次链接到结果链表中
        ListNode* res = head;
        while (p1 != NULL && p2 != NULL) {
            if (p1->val > p2->val) {
                head->next = p2;
                p2 = p2->next;
            } else {
                head->next = p1;
                p1 = p1->next;
            }
            head = head->next;
        }
        if (p1 == NULL) head->next = p2;
        else head->next = p1;
        return res;
    }

};

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla