【題目來源】https://www.acwing.com/problem/content/3642/【題目描述】給定兩個元素有序從小到大的鏈表要求將兩個鏈表合并成一個有序從小到大鏈表。【輸入格式】第一行輸入第一個鏈表的結(jié)點數(shù) S1。第二行輸入 S1 個整數(shù)兩兩之間用空格隔開。第三行輸入第二個鏈表的結(jié)點數(shù) S2。第四行輸入 S2 個整數(shù)兩兩之間用空格隔開?！据敵龈袷健枯敵龊喜⒅蟮逆湵斫Y(jié)果兩兩之間用空格隔開?！緮?shù)據(jù)范圍】1≤S1,S2≤100【輸入樣例】42 4 6 833 5 7【輸出樣例】2 3 4 5 6 7 8【算法分析】● 頭插法及尾插法頭插法創(chuàng)建單鏈表https://blog.csdn.net/hnjzsyjyj/article/details/120285274尾插法創(chuàng)建單鏈表https://blog.csdn.net/hnjzsyjyj/article/details/120285300● 結(jié)構(gòu)體構(gòu)造函數(shù)下面兩段代碼等價。第一段代碼為結(jié)構(gòu)體構(gòu)造函數(shù)寫法第二段代碼不是結(jié)構(gòu)體構(gòu)造函數(shù)寫法。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 */【算法代碼二數(shù)組模擬鏈表】#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/