輸入兩個(gè)遞增排序的鏈表,合并這兩個(gè)鏈表并使新鏈表中的結(jié)點(diǎn)仍然是按照遞增排序的。
成都創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)與策劃設(shè)計(jì),民權(quán)網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:民權(quán)等地區(qū)。民權(quán)做網(wǎng)站價(jià)格咨詢:18980820575
要合并兩個(gè)遞增的鏈表,首先找出兩個(gè)鏈表的頭結(jié)點(diǎn)中較小的一個(gè)就為合并后新鏈表的頭結(jié)點(diǎn),之后再依次將兩個(gè)鏈表中的結(jié)點(diǎn)值進(jìn)行相比較,依次將較小值在新鏈表中進(jìn)行尾插,直到其中一個(gè)鏈表遍歷完成,將剩余鏈表直接鏈在新鏈表的尾部就可以了,因?yàn)殒湵肀緛?lái)就是有序遞增的;
程序設(shè)計(jì)如下:
#include <iostream> #include <assert.h> using namespace std; template <class T> struct ListNode//鏈表結(jié)點(diǎn)結(jié)構(gòu) { T _data; ListNode<T>* _next; }; template <class T> ListNode<T>* buy_node(T data)//創(chuàng)建一個(gè)鏈表結(jié)點(diǎn) { ListNode<T>* tmp = new ListNode<T>; tmp->_data = data; tmp->_next = NULL; return tmp; } template <class T> void init_list(ListNode<T>** node, T data)//初始化鏈表 { *node = buy_node(data); } template <class T> void push_node(ListNode<T>*& head, T data)//插入鏈表結(jié)點(diǎn) { if(head == NULL) { init_list(&head, data); return; } ListNode<T>* tmp = head; while(tmp->_next != NULL) { tmp = tmp->_next; } tmp->_next = buy_node(data); } template <class T> void print_list(ListNode<T>* head)//打印鏈表 { while(head != NULL) { cout<<head->_data<<"->"; head = head->_next; } cout<<"NULL"<<endl; } template <class T> void destroy_list(ListNode<T>*& head)//銷毀鏈表 { if(head != NULL) { ListNode<T>* cur = head; ListNode<T>* tmp = head; while(cur != NULL) { tmp = cur; cur = cur->_next; delete tmp; } head = NULL; } } //實(shí)現(xiàn)1:循環(huán) template <class T> ListNode<T>* MergeList(ListNode<T>* list1, ListNode<T>* list2) { if(list1 == NULL)//條件判斷 return list2; else if(list2 == NULL) return list1; ListNode<T>* newHead = NULL; ListNode<T>* tmp1 = NULL; ListNode<T>* tmp2 = NULL; if(list1->_data <= list2->_data)//決定新鏈表的頭結(jié)點(diǎn) { newHead = list1; tmp1 = list1->_next; tmp2 = list2; } else { newHead = list2; tmp1 = list1; tmp2 = list2->_next; } ListNode<T>* cur = newHead; while((tmp1 != NULL) && (tmp2 != NULL)) { if(tmp1->_data <= tmp2->_data)//將較小值進(jìn)行尾插 { cur->_next = tmp1; cur = cur->_next; tmp1 = tmp1->_next; } else { cur->_next = tmp2; cur = cur->_next; tmp2 = tmp2->_next; } } if(tmp1 == NULL)//將剩下的鏈表直接接在新鏈表后面 cur->_next = tmp2; else cur->_next = tmp1; return newHead; } //實(shí)現(xiàn)2:遞歸 template <class T> ListNode<T>* MergeList(ListNode<T>* list1, ListNode<T>* list2) { if(list1 == NULL)//條件判斷 return list2; else if(list2 == NULL) return list1; ListNode<T>* newHead = NULL; if(list1->_data <= list2->_data) { newHead = list1; newHead->_next = MergeList(list1->_next, list2); } else { newHead = list2; newHead->_next = MergeList(list1, list2->_next); } return newHead; } int main() { ListNode<int>* list1 = NULL; push_node(list1, 1); push_node(list1, 2); push_node(list1, 3); push_node(list1, 8); push_node(list1, 11); push_node(list1, 14); ListNode<int>* list2 = NULL; push_node(list2, 5); push_node(list2, 6); push_node(list2, 7); push_node(list2, 8); push_node(list2, 9); cout<<"list1: "; print_list(list1); cout<<"list2: "; print_list(list2); ListNode<int>* newhead = MergeList(list1, list2); cout<<"merge list:"; print_list(newhead); destroy_list(list1); destroy_list(list2); return 0; }
運(yùn)行程序:
從上面程序可以看出來(lái),用遞歸比循環(huán)看起來(lái)更好理解和簡(jiǎn)潔。
《完》
分享標(biāo)題:合并兩個(gè)排序的鏈表——17
網(wǎng)站鏈接:http://muchs.cn/article40/gpphho.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供虛擬主機(jī)、微信公眾號(hào)、靜態(tài)網(wǎng)站、App開(kāi)發(fā)、手機(jī)網(wǎng)站建設(shè)、微信小程序
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)