PTA jmu-ds-有序链表合并（C/C++）

已知两个递增链表序列L1与L2，2个链表都是带头结点链表。设计函数实现L1，L2的合并，合并的链表仍然递增有序，头结点为L1的头结点。

合并后需要去除重复元素。（注意这个地方的处理）

• 输入格式:
  输入分两行，先输入数据项个数，再输入数据项，数字用空格间隔。
• 输出格式:
  在一行中输出合并后新的递增链表，数字间用空格分开，结尾不能有多余空格；

###你需要实现的函数为：

void MergeList(LinkList &L1,LinkList L2);//合并链表

• L1:递增链表L1
• L2:递增链表L2

裁判测试程序样例：

#include
using namespace std;
typedef int ElemType;
typedef struct LNode          //定义单链表结点类型
{
    ElemType data;
    struct LNode *next;        //指向后继结点
} LNode,*LinkList;
void CreateListR(LinkList &L, int n);//尾插法建链表
void DispList(LinkList L);//输出链表
void DestroyList(LinkList &L);//销毁链表
void MergeList(LinkList &L1,LinkList L2);
int main() 
{
  LinkList L1,L2;
  int n,m;
  cin>>n;
  CreateListR(L1,n);//尾插法建链表L1，细节不表
  cin>>m;
  CreateListR(L2,m);//尾插法建链表L2
  MergeList(L1,L2);//合并链表
  DispList(L1);//输出链表L1，细节不表
  DestroyList(L1);//销毁链表，细节不表
  return 0;
}

输入样例：

3 1 3 5
4 2 4 6 8

输出样例：

1 2 3 4 5 6 8

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

void MergeList(LinkList &L1, LinkList L2)
{
    LinkList L;
    L = (LNode *)malloc(sizeof(LNode));
    LNode *l1, *l2, *l3; 
    l1 = L1->next;      //l1指向L1的的第一个结点
    l2 = L2->next;      //l2指向L2的后继
    L = l3 = L1;
    while(l1 && l2)     //L1和L2都非空表
    {
        if(l1->data <= l2 -> data)    //l1的数据域小于l2就把l1插入到L中
        {
            l3->next = l1;
            l3 = l1;
            if(l1->data==l2->data)//如果两个元素的数据域相同就插入一个然后两个都往后移
				l2=l2->next;
            l1 = l1->next;
        }
        else                        //否则把l2插入到L中
        {
            l3->next = l2;
            l3 = l2;
            l2 = l2->next;
        }
    }
    l3->next = l1 ? l1:l2;
   
   free(L2);
    L1 = L;        //把L再返回给L1，打印的是L1
}

以上解法仅为个人理解，还有更简短的解法，后续会发，谢谢大家指正交流！