链表实现二路归并排序

通过链表实现二路归并排序

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){

    }
};

ListNode* merge(ListNode *list1,ListNode *list2){
    ListNode *list3 = NULL;
    ListNode *p=NULL;
    while(list1!=NULL&&list2!=NULL){
        if(list1->val<list2->val){
            if(list3==NULL){
                list3=list1;
                p=list3;
            }
            else{
                p->next=list1;
                p=p->next;
            }
            list1=list1->next;
    }

            else{
               if(list3==NULL){
                list3=list2;
                 p=list3;
            }
            else{
                p->next=list2;
                p=p->next;
            }
            list2=list2->next;
            }

}
    if(list1!=NULL){
        if(list3==NULL)
        {
            list3=list1;
            p=list3;
        }
        else
           p->next=list1;
    }
    if(list2!=NULL){
        if(list3==NULL)
        {
            list3=list2;
            p=list3;
        }
        else
        p->next=list2;
    }
    return list3;

}

ListNode* merge_sort(ListNode *list){
    if(list->next==NULL||list==NULL)
        return list;

    ListNode *p1 = list;
    ListNode *p2 = list->next;
    while(p2!=NULL&&p2->next!=NULL){
        p1 = p1->next;
        p2 = p2->next;
        while(p2!=NULL){
            p2 = p2->next;
        }
    }
    ListNode *p =p1->next;
    p1->next=NULL;
    list = merge_sort(list);
    p = merge_sort(p);
    ListNode* p3 = merge(list,p);
    return p3;
}


int main() {
    ListNode *list=new ListNode(0);
    ListNode *p;
    p=list;
    int n;
    cin>>n;
    while(n){
        int tmp;
        cin>>tmp;
        p->next= new ListNode(tmp);
        p=p->next;
        n--;
    }

    ListNode * res = merge_sort(list->next);
    while(res!=NULL){
        cout<<res->val<<" ";
        res = res->next;
    }
    return 0;

}