AcWing 3639：链表合并 ← 贵州大学考研机试题

【题目来源】https://www.acwing.com/problem/content/3642/【题目描述】给定两个元素有序从小到大的链表要求将两个链表合并成一个有序从小到大链表。【输入格式】第一行输入第一个链表的结点数 S1。第二行输入 S1 个整数两两之间用空格隔开。第三行输入第二个链表的结点数 S2。第四行输入 S2 个整数两两之间用空格隔开。【输出格式】输出合并之后的链表结果两两之间用空格隔开。【数据范围】1≤S1,S2≤100【输入样例】42 4 6 833 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* Lnew LinkNode(123);struct LinkNode { int data; LinkNode* next; }; LinkNode* Lnew LinkNode; L-data123; L-nextNULL;【算法代码一非链表写法】#includebits/stdc.h using namespace std; const int maxn205; int a[maxn]; int main() { int n; cinn; for(int i1; in; i) { cina[i]; } int p; cinp; for(int in1; inp; i) { cina[i]; } sort(a1,apn1); for(int i1; ipn; i) { couta[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 maxn210; int e[maxn],ne[maxn]; int a[maxn],b[maxn]; int main() { int n1,n2; cinn1; for(int i1; in1; i) { cina[i]; } cinn2; for(int i1; in2; i) { cinb[i]; } //Build linked list 1 for(int i1; in1; i) e[i]a[i]; for(int i1; in1; i) ne[i]i1; ne[n1]-1; int h11; //Build linked list 2 for(int i1; in2; i) e[n1i]b[i]; for(int i1; in2; i) ne[n1i]n1i1; ne[n1n2]-1; int h2n11; //merge int p1h1,p2h2; while(p1!-1 p2!-1) { if(e[p1]e[p2]) { coute[p1] ; p1ne[p1]; } else coute[p2] , p2ne[p2]; } while(p1!-1) { coute[p1] ; p1ne[p1]; } while(p2!-1) { coute[p2] ; p2ne[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* pnew LinkNode(x); LinkNode* rL; while(r-next) rr-next; r-nextp; } void print(LinkNode* L) { LinkNode* pL-next; while(p) { coutp-data ; pp-next; } } int main() { LinkNode* L1new LinkNode(-1); LinkNode* L2new LinkNode(-1); int n,m,x; cinn; for(int i1; in; i) { cinx; insert(L1,x); } cinm; for(int i1; im; i) { cinx; insert(L2,x); } LinkNode* ansnew LinkNode(-1); LinkNode* tans; LinkNode* pL1-next; LinkNode* qL2-next; while(q p) { if(p-data q-data) { t-nextp; pp-next; } else { t-nextq; qq-next; } tt-next; } if(p) t-nextp; if(q) t-nextq; 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.htmlhttps://www.acwing.com/problem/content/3642/https://www.acwing.com/solution/content/83605/