【练习】归并和冒泡两种方法c++将两个无序链表合并为一个升序的有序链表-蒲公英云

定义：

struct node { 
    int data;
    node* next;
};

新建有头指针的链表：

struct node *head;
head = NULL;//头指针初始为空
struct node *p;
//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p=(struct node *)malloc(sizeof(struct node));
scanf("%d",&a);
p->data=a;//将数据存储到当前结点的data域中
p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空

完整版本：

#include <stdio.h>
#include <stdlib.h>
//这里创建一个结构体用来表示链表的结点类型
struct node
{ 
int data;
struct node *next;
};
int main()
{ 
struct node *head,*p,*q,*t;
int i,n,a;
scanf("%d",&n);
head = NULL;//头指针初始为空
for(i=1;i<=n;i++)//循环读入n个数
{ 
scanf("%d",&a);
//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p=(struct node *)malloc(sizeof(struct node));
p->data=a;//将数据存储到当前结点的data域中
p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
if(head==NULL)
head=p;//如果这是第一个创建的结点，则将头指针指向这个结点
else
q->next=p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
q=p;//指针q也指向当前结点
}
//输出链表中的所有数
t=head;
while(t!=NULL)
{ 
printf("%d ",t->data);
t=t->next;//继续下一个结点
}
getchar();getchar();
return 0;
}

合并采用先分别升序后再进行合并两个有序链表，分别升序采用双指针和递归调用。先看用归并排序：

用归并排序：

node* merge(node* p,node*p2) { //这里是合并的排序
    node* src = new node;
 src->next = nullptr;
    //src->data = 0;
    node* now = src;
    node* a1 = p;
    node* a2 = p2;
    while (a1 != NULL && a2 != NULL) { 
        if (a1->data >= a2->data) { 
            node* tem = a2->next;
            src->next = a2;
            a2 = tem;
        }
        else { 
            node* tem = a1->next;
            src->next = a1;
            a1 = tem;
        }
        src = src->next;//合并两个有序链表 src->next=nullptr
    }
    if (a1 != NULL) src->next = a1;
    if (a2 != NULL)src->next = a2;
    return now->next;
}
node* merge_sort(node* p) { //这是将一个链表进行升序
    if (p == nullptr || p->next == nullptr) return p;
    node* fast = p;
    node* slow = new node;
    slow->data = 0;
    slow->next = p;
    while (fast != NULL && fast->next != NULL) { 
        fast = fast->next->next;
        slow = slow->next;
    }
    node* rhead = slow->next;
    slow->next = NULL;
    node* lh = merge_sort(p);
    node* rh = merge_sort(rhead);
    node* after = merge(lh, rhead);
    return after;
}
int main()
{ 
    srand(0);
    node* m = new node;
    m->data = rand()%5;
    //cout << m->data;
    node* n = new node;
    n->data = rand()%7;
    m->next = n;
    node* nn = new node;
    nn->data = rand()%8;
    n->next = nn;
    nn->next = nullptr;
    node* copy_m = m;
    cout << "第一个链表：";
    while (copy_m) { 
        cout << copy_m->data;
        copy_m = copy_m->next;
    }
    cout << endl;
    node* m2 = new node;
    m2->data =rand()%18;
    node* n2 = new node; 
    n2->data = rand() % 13;
    m2->next = n2;
    node* nn2 = new node;
    nn2->data = rand()%15;
    n2->next = nn2;
    nn2->next = nullptr;
    node* copy_n = m2;
    cout << "第二个链表：";
    while (copy_n) { 
        cout << copy_n->data;
        copy_n = copy_n->next;
    }
    cout << endl;
   node*one = merge_sort(m);
   node*two= merge_sort(m2);
    node* new_m = merge(one,two);
    node* nice = new_m;
    cout << endl;
    cout << "合并两个有序链表后的结果：";
    while (nice) { 
        cout << nice->data << "->";
        nice = nice->next;
    }
}

结果：
在这里插入图片描述

用冒泡排序：

node* merge_sort(node* p) { //这是将一个链表进行升序
    if (p == nullptr || p->next == nullptr) return p;
    node* mana = p;
    node* pp = mana;
    for (int i = 0; i < len(p) - 1; i++) { 
        mana = p;
        for (int j = 0; j < len(p) - i - 1; j++) { 
            node* t1 = mana;
            node* t2 = mana->next;
            if (t1->data > t2->data) { 
                int tem = t1->data;
                t1->data = t2->data;
                t2->data = tem;
            }
            mana = mana->next;
        }
    }
    return pp;
}
int main()
{ 
    srand(0);
    node* m = new node;
    m->data = rand()%12;
    //cout << m->data;
    node* n = new node;
    n->data = rand()%17;
    m->next = n;
    node* nn = new node;
    nn->data = rand()%18;
    n->next = nn;
    node* nnn = new node;
    nnn->data = rand() % 23;
    nnn->next = NULL;
    nn->next = nnn;
    node* copy_m = m;
    cout << "第一个链表：";
    while (copy_m) { 
        cout << copy_m->data<<"-";
        copy_m = copy_m->next;
    }
    cout << endl;
    node* m2 = new node;
    m2->data =rand()%18;
    node* n2 = new node; 
    n2->data = rand() % 13;
    m2->next = n2;
    node* nn2 = new node;
    nn2->data = rand()%15;
    n2->next = nn2;
    nn2->next = nullptr;
    node* copy_n = m2;
    cout << "第二个链表：";
    while (copy_n) { 
        cout << copy_n->data << "-";
        copy_n = copy_n->next;
    }
    cout << endl;
   node*one = merge_sort(m);
   node*two= merge_sort(m2);
    node* new_m = merge(one,two);
    node* nice = new_m;
    cout << endl;
    cout << "合并两个有序链表后的结果：";
    while (nice) { 
        cout << nice->data << "->";
        nice = nice->next;
    }
}