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

朴灿烈づ我的快乐病毒、 2022-05-30 04:45 154阅读 0赞

1.知识点：有序链表归并  
2.题意：分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据  
3.注意事项：注意若两个链表有一个为空链表的情况、注意合并时一个链表节点已经无节点和一个链表仍含有节点的情况

代码：

#include <stdio.h>
    #include <stdlib.h>
    struct st
    {
        int num;
        struct st *next;
    };
    struct st * f(struct st *head1, struct st *head2)
    {
        struct st *p1, *p2, *tail;
        p1 = head1 -> next;
        p2 = head2 -> next;
        head1 -> next = NULL;
        tail = head1;
        free(head2);/*释放申请的内存*/
        while(p1&&p2)/*两个链表都不为空*/
        {
            if(p1->num < p2->num)
            {
                tail -> next = p1;
                tail = p1;
                p1 = p1 -> next;
                tail -> next = NULL;
            }
            else if(p1->num >= p2->num)
            {
                tail -> next = p2;
                tail = p2;
                p2 = p2 -> next;
                tail -> next = NULL;
            }
        }
        /*判断那一个链表仍含有待插入节点*/
        if(p1)
            tail -> next = p1;
        else
            tail -> next = p2;
        return (head1);
    }
    int main()
    {
        struct st *head1, *head2, *p1, *p2, *tail1, *tail2;
        int M, N, i;
        head1 = (struct st*)malloc(sizeof(struct st));/*动态申请内存*/
        head2 = (struct st*)malloc(sizeof(struct st));/*动态申请内存*/
        p1 = head1 -> next;
        p2 = head2 -> next;
        scanf("%d %d", &M, &N);
        tail1 = head1;
        for(i = 0; i < M; i++)
        {
            p1 = (struct st *)malloc(sizeof(struct st));
            scanf("%d", &p1 -> num);
            /*顺序建立链表*/
            p1 -> next = NULL;
            tail1 -> next = p1;
            tail1 = p1;
    
        }
        tail2 = head2;
        for(i = 0; i < N; i++)
        {
            p2 = (struct st *)malloc(sizeof(struct st));
            scanf("%d", &p2 -> num);
            /*顺序建立链表*/
            p2 -> next = NULL;
            tail2 -> next = p2;
            tail2 = p2;
    
        }
        head1 = f(head1, head2);/*链表的归并*/
        p1 = head1 -> next;
        while(p1 != NULL)
        {
            printf("%d%c", p1->num, p1->next == NULL? '\n': ' ');
            p1 = p1->next;
        }
        return 0;
    }