【題目來源】https://www.acwing.com/problem/content/3642/【題目描述】給定兩個(gè)元素有序從小到大的鏈表要求將兩個(gè)鏈表合并成一個(gè)有序從小到大鏈表?！据斎敫袷健康谝恍休斎氲谝粋€(gè)鏈表的結(jié)點(diǎn)數(shù) S1。第二行輸入 S1 個(gè)整數(shù)兩兩之間用空格隔開。第三行輸入第二個(gè)鏈表的結(jié)點(diǎn)數(shù) S2。第四行輸入 S2 個(gè)整數(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à)。第一段代碼為結(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 */【參考文獻(xiàn)】https://www.cnblogs.com/Azurestars/p/15491714.htmlhttps://www.acwing.com/problem/content/3642/https://www.acwing.com/solution/content/83605/