本篇內(nèi)容主要講解“C++怎么實(shí)現(xiàn)混合插入有序鏈表”,感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“C++怎么實(shí)現(xiàn)混合插入有序鏈表”吧!
創(chuàng)新互聯(lián)專注于藍(lán)田企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站建設(shè),成都商城網(wǎng)站開(kāi)發(fā)。藍(lán)田網(wǎng)站建設(shè)公司,為藍(lán)田等地區(qū)提供建站服務(wù)。全流程按需開(kāi)發(fā)網(wǎng)站,專業(yè)設(shè)計(jì),全程項(xiàng)目跟蹤,創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
這道混合插入有序鏈表和我之前那篇混合插入有序數(shù)組非常的相似 Merge Sorted Array,僅僅是數(shù)據(jù)結(jié)構(gòu)由數(shù)組換成了鏈表而已,代碼寫(xiě)起來(lái)反而更簡(jiǎn)潔。具體思想就是新建一個(gè)鏈表,然后比較兩個(gè)鏈表中的元素值,把較小的那個(gè)鏈到新鏈表中,由于兩個(gè)輸入鏈表的長(zhǎng)度可能不同,所以最終會(huì)有一個(gè)鏈表先完成插入所有元素,則直接另一個(gè)未完成的鏈表直接鏈入新鏈表的末尾。代碼如下:
C++ 解法一:
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *dummy = new ListNode(-1), *cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return dummy->next; } };
Java 解法一:
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1), cur = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 != null) ? l1 : l2; return dummy.next; } }
下面我們來(lái)看遞歸的寫(xiě)法,當(dāng)某個(gè)鏈表為空了,就返回另一個(gè)。然后核心還是比較當(dāng)前兩個(gè)節(jié)點(diǎn)值大小,如果 l1 的小,那么對(duì)于 l1 的下一個(gè)節(jié)點(diǎn)和 l2 調(diào)用遞歸函數(shù),將返回值賦值給 l1.next,然后返回 l1;否則就對(duì)于 l2 的下一個(gè)節(jié)點(diǎn)和 l1 調(diào)用遞歸函數(shù),將返回值賦值給 l2.next,然后返回 l2,參見(jiàn)代碼如下:
C++ 解法二:
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } };
Java 解法二:
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
下面這種遞歸的寫(xiě)法去掉了 if 從句,看起來(lái)更加簡(jiǎn)潔一些,但是思路并沒(méi)有什么不同:
C++ 解法三:
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; ListNode *head = l1->val < l2->val ? l1 : l2; ListNode *nonhead = l1->val < l2->val ? l2 : l1; head->next = mergeTwoLists(head->next, nonhead); return head; } };
Java 解法三:
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head = (l1.val < l2.val) ? l1 : l2; ListNode nonhead = (l1.val < l2.val) ? l2 : l1; head.next = mergeTwoLists(head.next, nonhead); return head; } }
我們還可以三行搞定,簡(jiǎn)直喪心病狂有木有!
C++ 解法四:
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1 || (l2 && l1->val > l2->val)) swap(l1, l2); if (l1) l1->next = mergeTwoLists(l1->next, l2); return l1; } };
Java 解法四:
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null || (l2 != null && l1.val > l2.val)) { ListNode t = l1; l1 = l2; l2 = t; } if (l1 != null) l1.next = mergeTwoLists(l1.next, l2); return l1; } }
到此,相信大家對(duì)“C++怎么實(shí)現(xiàn)混合插入有序鏈表”有了更深的了解,不妨來(lái)實(shí)際操作一番吧!這里是創(chuàng)新互聯(lián)網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
本文標(biāo)題:C++怎么實(shí)現(xiàn)混合插入有序鏈表
分享URL:http://bm7419.com/article6/jciiig.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司、網(wǎng)站收錄、軟件開(kāi)發(fā)、用戶體驗(yàn)、微信公眾號(hào)
聲明:本網(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)