题目要求：

有两个按元素值递增有序排列的链表l1和l2，编写一个程序将l1表和l2表归并成一个按元素值递增有序的链表l3。要求（1）链表中允许有相同元素，只要链表l1,l2,l3单调不减即可；（2）要利用原表空间（即l1表和l2表）的结点空间构造表l3。

链表的最初状态

/*------------------------------- 7-3.c  -------------------------*/#include "stdio.h"/*定义int为ElemType类型*/typedef int ElemType;/*定义链表的结点类型*/typedef struct node{    ElemType data;			/*数据域*/    struct node *next;		/*指针域*/}LNode,*LinkList;/*创建一个长度为n的链表，并输入数据。此函数用来生成链表的头结点*/LinkList GreatLinkList(int n){    LinkList p,r,list=NULL;          ElemType e;        int i;    for(i=1;i<=n;i++){        scanf("%d",&e);        p=(LinkList)malloc(sizeof(LNode));        p->data=e;        p->next=NULL;        if(!list)            list=p;        else            r->next=p;        r=p;    }    return list;}/*向链表中插入结点，并向该结点的数据域中存放数据e，此函数用来生成链表时使用*/void insertList(LinkList *list,LinkList q,ElemType e){LinkList p;    p=( LinkList)malloc(sizeof(LNode));    p->data=e;    if(!*list){    *list=p;    p->next=NULL;    }    else{        p->next=q->next;        q->next=p;    }    }/*将p指向的结点插入到q1，q2所指向的结点中间*/void insertNode(LinkList *q1,LinkList *q2,LinkList *p,LinkList *l2){     if(*q1 == *q2)     {   /*插入结点的特殊情况*/         (*p)->next = *q2;         *l2 = *q2 = *q1 = *p;     }     else     {  /*实现将p指向的结点插入到q1、q2所指向的结点中间*/        (*q2)->next = *p;        (*p)->next = *q1;        (*q2) = (*q2)->next;   /*修改指针q2，使得q2始终指向q1的前一个结点*/     }}/*将链表l1，l2原空间有序归并，用l3返回*/void MergeLink(LinkList l1, LinkList l2 ,LinkList *l3){    /*将链表l1,l2有序归并，l3指向归并后的新链表*/    LinkList p,q1,q2;    q1 = q2  = l2; /*l3指向l2*/    p = l1;    while(p!=NULL && q1!=NULL){        if(p->data >= q1->data) {        q2 = q1;        q1 = q1->next;        }        else{            l1 = l1->next;				/*链表l1删除头结点*/            insertNode(&q1,&q2,&p,&l2); 	/*将p指向的结点插到q2之前q1之后*/            p = l1; 						/*p指向下一个结点*/        }    }    if(q1 == NULL) q2->next = p;   		/*将l1的剩余尾链归并到l2中*/    *l3 = l2;}main(){    ElemType e;    LinkList  l1,l2,l3,q;    printf("Please input the contents of Link1\n");    /*生成链表l1*/    q=l1=GreatLinkList(1);   	/*创建一个链表结点，q和l1指向该结点*/    scanf("%d",&e);    while(e)               		/*循环地输入数据，同时插入新生成的结点*/    {      insertList(&l1,q,e) ;      q=q->next;      scanf("%d",&e);    }printf("Please input the contents of Link2\n");/*生成链表l2*/    q=l2=GreatLinkList(1);   	/*创建一个链表结点，q和l2指向该结点*/    scanf("%d",&e);    while(e)               		/*循环地输入数据，同时插入新生成的结点*/    {      insertList(&l2,q,e) ;      q=q->next;      scanf("%d",&e);    }    MergeLink(l1,l2,&l3);  		/*合并l2，l2并用l3指向合并后的链表*/    q = l3;    printf("The merge of link1 and link 2 is\n");    while(q)            			/*打印出合并后的链表*/    {        printf("%d ",q->data) ;        q = q->next;    }    getche();}	

运行结果：

运行结果