【题目来源】
https://www.acwing.com/problem/content/3642/

【题目描述】
给定两个元素有序（从小到大）的链表，要求将两个链表合并成一个有序（从小到大）链表。

【输入格式】
第一行输入第一个链表的结点数 S1。
第二行输入 S1 个整数，两两之间用空格隔开。
第三行输入第二个链表的结点数 S2。
第四行输入 S2 个整数，两两之间用空格隔开。

【输出格式】
输出合并之后的链表结果，两两之间用空格隔开。

【数据范围】
1≤S1,S2≤100

【输入样例】
4
2 4 6 8
3
3 5 7

【输出样例】
2 3 4 5 6 7 8

【算法分析】
● 头插法及尾插法
头插法创建单链表：https://blog.csdn.net/hnjzsyjyj/article/details/120285274
尾插法创建单链表：https://blog.csdn.net/hnjzsyjyj/article/details/120285300
● 结构体构造函数
下面两段代码等价。第一段代码为结构体构造函数写法，第二段代码不是结构体构造函数写法。

struct LinkNode { int data; LinkNode* next; LinkNode(int x):data(x),next(NULL) {} }; LinkNode* L=new LinkNode(123);

struct LinkNode { int data; LinkNode* next; }; LinkNode* L=new LinkNode; L->data=123; L->next=NULL;

【算法代码一：非链表写法】

#include<bits/stdc++.h> using namespace std; const int maxn=205; int a[maxn]; int main() { int n; cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; } int p; cin>>p; for(int i=n+1; i<=n+p; i++) { cin>>a[i]; } sort(a+1,a+p+n+1); for(int i=1; i<=p+n; i++) { cout<<a[i]<<" "; } return 0; } /* in: 4 2 4 6 8 3 3 5 7 out: 2 3 4 5 6 7 8 */

【算法代码二：数组模拟链表】

#include <bits/stdc++.h> using namespace std; const int maxn=210; int e[maxn],ne[maxn]; int a[maxn],b[maxn]; int main() { int n1,n2; cin>>n1; for(int i=1; i<=n1; i++) { cin>>a[i]; } cin>>n2; for(int i=1; i<=n2; i++) { cin>>b[i]; } //Build linked list 1 for(int i=1; i<=n1; i++) e[i]=a[i]; for(int i=1; i<n1; i++) ne[i]=i+1; ne[n1]=-1; int h1=1; //Build linked list 2 for(int i=1; i<=n2; i++) e[n1+i]=b[i]; for(int i=1; i<n2; i++) ne[n1+i]=n1+i+1; ne[n1+n2]=-1; int h2=n1+1; //merge int p1=h1,p2=h2; while(p1!=-1 && p2!=-1) { if(e[p1]<e[p2]) { cout<<e[p1]<<" "; p1=ne[p1]; } else cout<<e[p2]<<" ", p2=ne[p2]; } while(p1!=-1) { cout<<e[p1]<<" "; p1=ne[p1]; } while(p2!=-1) { cout<<e[p2]<<" "; p2=ne[p2]; } return 0; } /* in: 4 2 4 6 8 3 3 5 7 out: 2 3 4 5 6 7 8 */

【算法代码三：纯链表写法】

#include <bits/stdc++.h> using namespace std; struct LinkNode { int data; LinkNode* next; LinkNode(int x):data(x),next(NULL) {} }; void insert(LinkNode* L, int x) { LinkNode* p=new LinkNode(x); LinkNode* r=L; while(r->next) r=r->next; r->next=p; } void print(LinkNode* L) { LinkNode* p=L->next; while(p) { cout<<p->data<<" "; p=p->next; } } int main() { LinkNode* L1=new LinkNode(-1); LinkNode* L2=new LinkNode(-1); int n,m,x; cin>>n; for(int i=1; i<=n; i++) { cin>>x; insert(L1,x); } cin>>m; for(int i=1; i<=m; i++) { cin>>x; insert(L2,x); } LinkNode* ans=new LinkNode(-1); LinkNode* t=ans; LinkNode* p=L1->next; LinkNode* q=L2->next; while(q && p) { if(p->data < q->data) { t->next=p; p=p->next; } else { t->next=q; q=q->next; } t=t->next; } if(p) t->next=p; if(q) t->next=q; print(ans); return 0; } /* in: 4 2 4 6 8 3 3 5 7 out: 2 3 4 5 6 7 8 */

【参考文献】
https://www.cnblogs.com/Azurestars/p/15491714.html
https://www.acwing.com/problem/content/3642/
https://www.acwing.com/solution/content/83605/