链表合并c++

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

typedef int Status;

typedef struct lnode

{

    int sno;

    int grade;

    struct lnode* next;

}lnode, * linklist;

Status init_list(linklist& l)

{

    l = new lnode;

    l->next = NULL;

    return 0;

}

void create_list(linklist& l, int n)

{

    lnode * r = l;

    for (int i = 0; i < n; i++)

    {

        lnode* p = new lnode;

        cin >> p->sno >> p->grade;

        r->next = p;

        p->next = NULL;

        r = p;

    }

}

void fun(linklist& l)//无序单链表从小到大的排序

{

    lnode* p, * q;

    p = l->next;

    while (p != NULL)

    {

        q = p->next;

        while (q != NULL)

        {

            if (q->sno < p->sno)

            {

                int t = q->sno;

                q->sno = p->sno;

                p->sno = t;

                int m = q->grade;

                q->grade = p->grade;

                p->grade = m;

            }

            q = q->next;

        }

        p = p->next;

    }

}

void insert_list(linklist& l1, linklist& l2) //将无序链表插入到有序链表当中

{

    lnode* p = l1->next;

    lnode* q = l2->next;

    lnode* m, * n=l1;

    while (q != NULL)

    {

        if (q->sno <= p->sno)

        {

            m = q->next;

            q->next = p;

            l1->next = q;

            p = q;

            q = m;

        }

        else

        {

            while (q->sno > p->sno && p->next != NULL)

            {

                n = p;

                p = p->next;

            }

            if (q->sno < p->sno)//当l1链表中有元素大于q结点的内容时，将q结点插在l1链表中间

            {

                m = q->next;

                q->next = p;

                n->next = q;

                q = m;

                p = l1->next;

            }

            else //当l2链表中的元素大于l1链表中所有的元素时，将该结点插在l1链表的末尾

            {

                m = q->next;

                p->next = q;

                q->next = NULL;

                q = m;

            }

        }

    }

}

void print(linklist l)

{

    lnode* p = l->next;

    while (p != NULL)

    {

        cout << p->sno << ' ' << p->grade << endl;

        p = p->next;

    }

}

int main()

{

    linklist l1, l2;

    init_list(l1);

    init_list(l2);

    int n, m;

    cin >> n >> m;

    create_list(l1, n);

    create_list(l2, m);

    fun(l1);

    insert_list(l1, l2);

    print(l1);

    return 0;

}