golang中怎么合并K個排序鏈表

這篇文章給大家介紹golang中怎么合并K個排序鏈表，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

創(chuàng)新互聯(lián)專注于夾江企業(yè)網(wǎng)站建設,成都響應式網(wǎng)站建設公司,商城系統(tǒng)網(wǎng)站開發(fā)。夾江網(wǎng)站建設公司,為夾江等地區(qū)提供建站服務。全流程定制網(wǎng)站，專業(yè)設計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務

合并 k 個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復雜度。

示例:

輸入:

[

  1->4->5,

  1->3->4,

  2->6

]

輸出: 1->1->2->3->4->4->5->6

解題思路：

這是一個數(shù)組＋鏈表組合題目，看到鏈表有序，我們首先想到鏈表合并子問題

1，這是合并兩個有序鏈表的基礎上的擴展

2，簡單思路

將依次將第二個起都合并到第一個，復雜度O（k*n）

3，思路二，兩兩合并，復雜度O（logk*n）

4，注意長度可能是奇數(shù)，即使是偶數(shù)，兩兩合并后可能是奇數(shù),需要特殊處理，否則數(shù)組越界問題很難處理，很容易死循環(huán)

5，擴展思路

用優(yōu)先隊列，每次取最小的元素合并，然后把當前鏈表下一個元素入隊，直到隊列為空

代碼實現(xiàn)

/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func mergeKLists(lists []*ListNode) *ListNode {    k:=len(lists)    if k==0{        return nil    }    for k>1{        if k%2==1{                lists[0]=merge(lists[0],lists[k-1])        }        k/=2        for i:=0;i<k;i++{            lists[i]=merge(lists[k+i],lists[i])        }
    }    return lists[0]}
func merge(l1,l2 *ListNode)*ListNode{    h:=&ListNode{}    tmp:=h    for l1!=nil && l2!=nil{        if l1.Val<l2.Val{            tmp.Next=l1            l1=l1.Next        }else{            tmp.Next=l2            l2=l2.Next        }        tmp=tmp.Next    }    if l1!=nil{        tmp.Next=l1    }        if l2!=nil{        tmp.Next=l2    }    return h.Next}

關于golang中怎么合并K個排序鏈表就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

本文標題：golang中怎么合并K個排序鏈表
轉載源于：http://muchs.cn/article22/pidhcc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供電子商務、網(wǎng)站設計、做網(wǎng)站、動態(tài)網(wǎng)站、品牌網(wǎng)站制作、網(wǎng)站排名

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)