7-1 两个有序链表序列的合并（20 分)

86 阅读 0 评论 57 点赞

我是靠谱客的博主狂野盼望，最近开发中收集的这篇文章主要介绍7-1 两个有序链表序列的合并（20 分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

7-1 两个有序链表序列的合并（20 分)
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式: 在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:
1 3 5 -1
2 4 6 8 10 -1
输出样例:
1 2 3 4 5 6 8 10

答案（c++）

#include<iostream>
using namespace std;

typedef struct NLode {
int data;
NLode* next;
}NLode, * LinkList;

void Creta(LinkList& L) {
   L = new NLode;
   LinkList p, a;
   L->next = NULL;
   a = L;
   int i;
   while (1) {
       cin >> i;
       if (i != -1) {
           p = new NLode;
           p->data = i;
           p->next = NULL;
           a->next = p;
           a = p;
       }
       else {
           break;
       }
   }
}

void Print(LinkList L) {
   LinkList a;
   a = L->next;
   while (a) {
       cout << a->data;
       a = a->next;
       if (a)
           cout << " ";
   }
}
void MergeList(LinkList& LA, LinkList& LB, LinkList& LC) {
   LC = LA;
   LinkList a=LA->next, b=LB->next,c=LC;
   while (a&&b)
   {
       if (a->data < b->data) {
           c->next = a;
           c = c->next;
           a = a->next;
       }
       else
       {
           c->next = b;
           c = c->next;
           b = b->next;
       }
   }
   c->next = a ? a : b;
   delete LB;
}

int main() {
   LinkList L = NULL;
   LinkList N = NULL;
   LinkList M = NULL;
   Creta(L);
   Creta(N);
   MergeList(L, N, M);
   Print(M);
   return 0;
}