链表排序算法（归并和快排）

你的名字 2022-09-14 15:15 198阅读 0赞

### 链表排序算法（归并和快排） ###

*  归并
 *  快排

# 归并 #

class Solution
    {
    public:
        ListNode *sortList(ListNode *head)
        {
            if (head == NULL || head->next == NULL)
            {
                return head;
            }
            return mergeSort(head);
        }
    
        ListNode *mergeSort(ListNode *head)
        {
    
            if (head == NULL)
            {
                return NULL;
            }
            if (head->next == NULL)
            {
                return head;
            }
            ListNode *slow = head;
            ListNode *fast = head->next;
            while (fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
    
            ListNode *r_head = slow->next;
            slow->next = NULL;
            ListNode *left = mergeSort(head);
            ListNode *right = mergeSort(r_head);
            return mergeTogether(left, right);
        }
    
        ListNode *mergeTogether(ListNode *head1, ListNode *head2)
        {
            if (head1 == NULL)
            {
                return head2;
            }
            if (head2 == NULL)
            {
                return head1;
            }
            ListNode *root = new ListNode(0);
            ListNode *h = root;
            while (head1 && head2)
            {
                if (head1->val < head2->val)
                {
                    h->next = head1;
                    head1 = head1->next;
                }
                else
                {
                    h->next = head2;
                    head2 = head2->next;
                }
                h = h->next;
            }
            if (head1)
            {
                h->next = head1;
            }
            if (head2)
            {
                h->next = head2;
            }
            return root->next;
        }
    };

# 快排 #

void quickSort(ListNode *head, ListNode *tail)
    {
        if(head==tail||head->next==tail)
        {
            return;
        }
        int pivot = head->val;
        ListNode *left = head;
        ListNode *cur = head->next;
    
        while(cur!=tail)
        {
            if(cur->val<pivot)
            {
                left = left->next;
                swap(left->val, cur->val);
            }
            cur = cur->next;
        }
        swap(left->val, head->val);
    
        quickSort(head, left);
        quickSort(left->next, tail);
    }
    
    ListNode *sortList(ListNode *head)
    {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
    
        quickSort(head, NULL);
    
        return head;
    }