数据结构实验之链表四：有序链表的归并

Dear 丶 2022-05-17 11:46 152阅读 0赞

数据结构实验之链表四：有序链表的归并

Time Limit: 1000 ms Memory Limit: 65536 KiB  
Submit Statistic  
Problem Description  
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。  
Input  
第一行输入M与N的值；  
第二行依次输入M个有序的整数；  
第三行依次输入N个有序的整数。  
Output  
输出合并后的单链表所包含的M+N个有序的整数。  
Sample Input  
6 5  
1 23 26 45 66 99  
14 21 28 50 100  
Sample Output  
1 14 21 23 26 28 45 50 66 99 100  
Hint  
不得使用数组！  
Source

#include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    typedef struct LNode{
        int data;
        struct LNode *next; 
    }*LinkList,LNode;
    LinkList createLinkList(LinkList &head,int n){
        LNode *tail,*p;
        head =tail = (LinkList)malloc(sizeof(LNode));
        head->next = NULL;
        tail = head;
        for (int i=0;i<n;i++)
        {
            p = (LinkList)malloc(sizeof(LNode));
            p->next = NULL;
            scanf("%d",&p->data);
            tail->next = p;
            tail = p;
        }
        return head;
    
    }
    void display(LinkList p){
        p=p->next;
        while(p){
            if (p->next)
            {
                printf("%d ",p->data);
            }else{
                printf("%d\n",p->data);
            }
            p = p->next;
        }
    
    }
    LinkList merge_LinkList(LinkList list1,LinkList list2){
        LNode *p1 = list1->next;
        LNode *p2 = list2->next;
        list1->next = NULL;
        LNode *p,*tail;
        tail = list1;
        while(p1 && p2){
    
            if (p1->data < p2->data)
            {
                tail->next = p1;
                tail = p1;
                **//这里千万不能加tail->next=NULL, 与"tail->next = p1"冲突**
                p1 = p1->next;
            }else{
                tail->next = p2;
                tail = p2;
                p2 = p2->next;
            }
        }
        if (p1)
        {
            tail->next = p1;
        }
        if (p2)
        {
            tail->next = p2;
        }
        return list1;
    
    }
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        LinkList linklist = NULL,list2=NULL;
        createLinkList(linklist,n);
        createLinkList(list2,m);
    display(merge_LinkList(linklist,list2));
        return 0;
    }