两个有序链表的合并.png

两个有序链表的合并

要求

• 给定两个有序链表，将两个链表合并为一个有序链表

思路

• 对于给定的链表l1和链表l2。定义一个链表l3来存储合并后的两个链表。
• 定义两个指针，分别指向两个链表的头结点，在两个链表都不为空时，
  • 比较两个链表结点的值的大小。
  • 若链表l1的节点大于l2的节点，则将l1的节点值赋值给l3。l1的指针指向下一个节点。
  • 反之，则则将l2的节点值赋值给l3。l2的指针指向下一个节点。
• 两个链表出现一个为空时，判断哪个不为空，将该链表剩下的节点全部赋值给l3。

图解

• 两个有序链表的合并图解.png

代码

#include <stdio.h>
#include <malloc.h>

//构造结构体
typedef struct list
{
    int data;
    struct list *next;
}*List,LNode;

//函数声明
List init_list(List head,int num);
void print_list(List head);
List merge(List l1,List l2);

void main()
{
    List l,l1,l2;
    l1 = (LNode*)malloc(sizeof(LNode));
    l1 = init_list(l1,3);
    l2 = (LNode*)malloc(sizeof(LNode));
    l2 = init_list(l2,7);
    l = merge(l1,l2);
    print_list(l);

}

//两个有序链表合并函数
/*
List merge(List l1,List l2)
{
    List head,p,s;
    head = (List)malloc(sizeof(LNode));
    p = head;
    while(l1 != NULL && l2 != NULL)
    {
        s = (List)malloc(sizeof(LNode));
        if(l1->data > l2->data)
        {
            s ->data = l2->data;
            l2 = l2->next;
        }else{
            s ->data = l1->data;
            l1 = l1->next;
        }
        s->next = NULL;
        p->next = s;
        p = p->next;
    }
    while(l1 != NULL)
    {
        s = (List)malloc(sizeof(LNode));
        s->data = l1->data;
        l1 = l1->next;
        s->next = NULL;
        p->next = s;
        p = p->next;
    }
    while(l2 != NULL)
    {
        s = (List)malloc(sizeof(LNode));
        s->data = l2->data;
        l2 = l2->next;
        s->next = NULL;
        p->next = s;
        p = p->next;
    }
    return head->next;
}
*/

//两个有序链表合并函数优化
List merge(List l1,List l2)
{
    List head,p,s;
    head = (List)malloc(sizeof(LNode));
    p = head;
    while(l1 != NULL || l2 != NULL)
    {
        s = (List)malloc(sizeof(LNode));
        if(l1 != NULL && l1->data <= l2->data)
        {
            s ->data = l1->data;
            l1 = l1->next;
        }else{
            s ->data = l2->data;
            l2 = l2->next;
        }
        s->next = NULL;
        p->next = s;
        p = p->next;
    }
    return head->next;
}

//链表初始化函数
List init_list(List head,int num)
{
    int i = 1;
    List p = head;
    while(i <= num)
    {
        List s;
        s = (LNode*)malloc(sizeof(LNode));
        s->data = i * num;
        s->next = NULL;
        p->next = s;
        p = p->next;
        i++;
    }
    return head->next;
}

//链表输出函数
void print_list(List head)
{
    List p;
    p = head;
    while(p != NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}