【单链表】非递减有序集合合并

描述

巳知线性表LA和线性表LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。

输入三行,第一行A,B集合的个数n,m
第二行:集合A的数据;
第三行:集合B的数据。输出二行,第一行,集合C的个数k
第二行:集合C的数据。样例输入

11   12
2 4 6 7 8 9 12 34 56 78 89
3 5 7 9 12 34 56 98 234 456 789 1234

样例输出

18
2 3 4 5 6 7 8 9 12 34 56 78 89 98 234 456 789 1234

提示n,m<255

 

#include<iostream>
using namespace std;
int muti = 0;
struct Node
{
  int data;
  Node *next;
};
struct LinkList
{
public:
  LinkList();
  void Insert(int n);
  void reList();
  void printList();
private:
  Node *p, *s, *first,*r;
};

LinkList::LinkList()
{
  first = new Node;
  first->next = NULL;
}

void LinkList::Insert(int n)
{
  Node *front;
  s = new Node;
  s->data = n;
  front = first;
  p = first->next;
  while (p && n>=p->data)
  {
    if (n == p->data)
    {
      muti++;
      delete s;
      return;
    }
    front = p;
    p = p->next;
  }
  s->next = p;
  front->next = s;
  return;
}


void LinkList::reList()
{
  p = first->next;
  first->next = NULL;
  while (p)
  {
    s = p->next;
    p->next = first->next;
    first->next = p;
    p = s;
  }
}

void LinkList::printList()
{
  p = first->next;
  while (p)
  {
    printf("%d ", p->data);
    p = p->next;
    
  }
  cout << endl;
}

int main()
{
  muti = 0;
  int a = 0, b = 0,temp=0;
  cin >> a >> b;
  LinkList myList;
  for (int i = 0; i < a+b; i++)
  {
    cin >> temp;
    myList.Insert(temp);
  }
  cout << a + b - muti << endl;
  myList.printList();
  
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

4 × 2 =