C++怎么实现3个链表排序整合到一起

本篇内容介绍了“C++怎么实现3个链表排序整合到一起”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

当两个 递增链表时 可以采用 归并排序 或者 二叉树建立时候的递归。

#include <iostream>
#include <cstring>
using namespace std;
typedef struct node
{
    int data;
    struct node* next;
}NODE;

NODE* CreateList(int a[], int n)
{
    NODE* p;
    NODE* q;
    NODE* head;
    p = new NODE;
    p->data = a[0];
    head = p;
    for(int i=1;i<n;i++)
    {
        q = new NODE;
        q->data = a[i];
        p->next = q;
        p = q;
    }
    p->next = NULL;
    return head;
}

//整体思路跟 排序算法中的 归并排序类似
NODE* MerageList(NODE* head_1, NODE* head_2)
{
    NODE* head_3 = NULL;
    if(head_1 == NULL)
    {
        head_3 = head_2;
    }
    else if(head_2 == NULL)
    {
        head_3 = head_1;
    }
    else
    {
        NODE* top1 =head_1;
        NODE* top2 =head_2;
        NODE* mid = NULL;
        if(top1->data < top2->data)
        {
            head_3 = top1;
             mid =head_3  ;
            top1 = top1->next;
        }
        else
        {
            head_3 = top2;
             mid = head_3  ;
            top2 = top2->next;
        } // 找到合并后头节点

        while(top1 && top2)
        {

            if(top1->data < top2->data)
            {
                mid->next = top1;
                mid = top1;
                top1 = top1->next;
            }
            else
            {
                mid->next = top2;
                mid = top2;
                top2 = top2->next;
            }
        }
        if(top1)
        {
            mid->next = top1;
        }
       else  if(top2)
        {
            mid->next = top2;
        }
    }
    return head_3;
}

//我们可以采用二叉树插入时的 递归法
NODE* MerageByDG(NODE* head_1, NODE* head_2)
{
    if(NULL == head_1)
    {
        return head_2;
    }
    else if(NULL == head_2)
    {
        return head_1;
    }
    NODE* head_3;
    if(head_1->data < head_2->data)
    {
        head_3 = head_1;
        head_3->next = MerageByDG(head_1->next, head_2);
    }
    else
    {
        head_3 = head_2;
        head_3->next = MerageByDG(head_1, head_2->next);
    }
    return head_3;
}

int main()
{
    int a[]={1,3,5,7};
    int c[]={2,4,6,8,10};
    NODE* list1 = CreateList(a,4);
    NODE* list3 = CreateList(c,5);
    list1=MerageByDG(list1, list3);
    for(NODE* temp =list1;temp; temp = temp->next)
    {
        cout<< temp->data<<" ";
    }
    cout<<endl;
    return 0;
}

普通数据时可用如下方法 用冒泡排序法

#include <iostream>
#include <cstring>
using namespace std;
typedef struct node
{
    int data;
    struct node* next;
}NODE;
NODE* CreateList(int a[], int n)
{
    NODE* p;
    NODE* q;
    NODE* head;
    p = new NODE;
    p->data = a[0];
    head =p;
    for(int i=1;i<n;i++)
    {
        q = new NODE;
        q->data = a[i];
        p->next = q;
        p = q;
    }
    p->next = NULL;
    return head;
}
void BubbleSort(NODE* list)
{
    for(NODE* temp1= list;temp1; temp1=temp1->next)
    {
        for(NODE* temp2 =temp1->next; temp2; temp2=temp2->next)
        {
            if(temp1->data >temp2->data)
            {
                int temp = temp1->data;
                temp1->data = temp2->data;
                temp2->data = temp;
            }
        }
    }
}
NODE* Merge (NODE* list1, NODE* list2)
{

    NODE* temp2=list2;
    NODE* temp1=list1;
    NODE* front=NULL;
    for(;temp2; temp2 = temp2->next)
    {
        for(;  temp1;  front = temp1,temp1=temp1->next)
        {
            if(  ((temp2->data)  < (temp1->data)) && (front==NULL))
            {
                NODE* temp = new NODE;
                temp->data = temp2->data;
                temp->next = list1;
                list1 = temp;
                break;
            }
            else if( (front != NULL) && (front->data < temp2->data) &&  (temp1->data >= temp2->data) )
            {
                NODE* temp = new NODE;
                temp->data = temp2->data;
                temp->next = temp1;
                front->next = temp;
                break;
            }
            else if ( ( (temp2->data)>(temp1->data) ) && (NULL==temp1->next)  )
            {
                NODE* temp = new NODE;
                temp->data = temp2->data;
                temp1->next = temp;
                temp->next =NULL;
                break;
            }
        }
        temp1 = list1;
        front = NULL;
    }
    return list1;
}
int main()
{
    int a[]={5,6,6,7};
    int b[]={8,6,4,1};
     int c[]={3,5,6,7,8};
    NODE* list1 = CreateList(a,4);
    NODE* list2 = CreateList(b,4);
    NODE* list3 = CreateList(c,5);
    list1=Merge(list1, list2);
    list1=Merge(list1,list3);
    for(NODE* temp =list1;temp; temp = temp->next)
    {
        cout<< temp->data<<" ";
    }
    cout<<endl;
    BubbleSort(list2);
    for(NODE* temp = list2; temp;  temp=temp->next)
    {
        cout<< temp->data<<" ";
    }
    cout<<endl;
    return 0;
}

“C++怎么实现3个链表排序整合到一起”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！