Sort List（C++排序链表）

- 日理万妓 2022-10-04 13:55 171阅读 0赞

（1）归并排序

/**
     * 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* merge(ListNode *head1,ListNode *head2) {
            ListNode *n_head=new ListNode(0);
            ListNode *h_head=n_head;
            while(head1!=nullptr && head2!=nullptr) {
                if(head1->val<head2->val) {
                    ListNode *temp=head1->next;
                    h_head->next=head1;
                    head1=temp;
                } else if(head1->val>head2->val) {
                    ListNode *temp=head2->next;
                    h_head->next=head2;
                    head2=temp;
                } else {
                    ListNode *temp=head1->next;
                    ListNode *temp1=head2->next;
                    h_head->next=head1;
                    h_head=h_head->next;
                    h_head->next=head2;
                    head1=temp;
                    head2=temp1;
                }
                h_head=h_head->next;
            }
     
            if(head1!=nullptr) {
                h_head->next=head1;
            } else if(head2!=nullptr) {
                h_head->next=head2;
            } else h_head->next=nullptr;
            return n_head->next;
        }
        
        ListNode *helper(ListNode* head,ListNode *tail) {
            if(head==nullptr) return head;
            if(head->next==tail) {
                head->next=nullptr;
                return head;
            }
            ListNode *slow=head,*fast=head;
            while(fast!=tail) {
                slow=slow->next;
                fast=fast->next;
                if(fast!=tail) {
                    fast=fast->next;
                }
            }
            ListNode *mid=slow;
            return merge(helper(head,mid),helper(mid,tail));
        }
        
        ListNode* sortList(ListNode* head) {
            return helper(head,nullptr);
        }
    };