兩個有序鏈表的合并.png

兩個有序鏈表的合并

要求

• 給定兩個有序鏈表，將兩個鏈表合并為一個有序鏈表

思路

• 對于給定的鏈表l1和鏈表l2。定義一個鏈表l3來存儲合并后的兩個鏈表。
• 定義兩個指針，分別指向兩個鏈表的頭結(jié)點，在兩個鏈表都不為空時，
  • 比較兩個鏈表結(jié)點的值的大小。
  • 若鏈表l1的節(jié)點大于l2的節(jié)點，則將l1的節(jié)點值賦值給l3。l1的指針指向下一個節(jié)點。
  • 反之，則則將l2的節(jié)點值賦值給l3。l2的指針指向下一個節(jié)點。
• 兩個鏈表出現(xiàn)一個為空時，判斷哪個不為空，將該鏈表剩下的節(jié)點全部賦值給l3。

圖解

• 兩個有序鏈表的合并圖解.png

代碼

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

//構(gòu)造結(jié)構(gòu)體
typedef struct list
{
    int data;
    struct list *next;
}*List,LNode;

//函數(shù)聲明
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);

}

//兩個有序鏈表合并函數(shù)
/*
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;
}
*/

//兩個有序鏈表合并函數(shù)優(yōu)化
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;
}

//鏈表初始化函數(shù)
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;
}

//鏈表輸出函數(shù)
void print_list(List head)
{
    List p;
    p = head;
    while(p != NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}