這篇文章主要講解了“c++如何合并有序鏈表”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“c++如何合并有序鏈表”吧！
成都創(chuàng)新互聯(lián)公司主要從事做網(wǎng)站、網(wǎng)站制作、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)沙坡頭,十年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):13518219792
算法：
算法的核心在于兩個(gè)有序鏈表的合并操作，K個(gè)有序鏈表的合并只是一個(gè)變形題目，先拆分成k/2個(gè)有序鏈表，然后等比數(shù)列減少到1個(gè)數(shù)列。
題目1:合并兩個(gè)有序鏈表
代碼實(shí)現(xiàn)：
// 算法： 遞歸的算法，l1=l2的話，偏移l2.Next，然后遞歸l2.Next與l1的操作。/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } if l1.Val < l2.Val { l1.Next = mergeTwoLists(l1.Next, l2) return l1 } l2.Next = mergeTwoLists(l1,l2.Next) return l2}
‘題目2: 合并k個(gè)排序鏈表
代碼實(shí)現(xiàn)：
/*解法二：分治+遞歸；分治：兩個(gè)一組，依次遞減，k,k/2,k/4,k/8...1;遞歸：兩個(gè)列表一組，排序*//** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func mergeKLists(lists []*ListNode) *ListNode { if len(lists) == 0 { return nil } if len(lists) == 1 { return lists[0] } for { n := len(lists)/2 ok := len(lists)%2 == 1 for i:=0;i< n; i++ { lists[i]=mergeLists(lists[i],lists[i+n]) } if !ok { lists = lists[:n] } else { lists[n] = lists[len(lists)-1] lists = lists[:n+1] } if len(lists) == 1 { break } } return lists[0]}
func mergeLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } if l1.Val < l2.Val { l1.Next = mergeLists(l1.Next, l2) return l1 }
l2.Next = mergeLists(l1, l2.Next) return l2}
感謝各位的閱讀，以上就是“c++如何合并有序鏈表”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)c++如何合并有序鏈表這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
文章名稱：c++如何合并有序鏈表
網(wǎng)站URL：
http://weahome.cn/article/ipppjd.html
重慶分公司
重慶分公司
