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

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

合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。

示例:

輸入:

[

  1->4->5,

  1->3->4,

  2->6

]

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

解題思路：

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

1，這是合并兩個(gè)有序鏈表的基礎(chǔ)上的擴(kuò)展

2，簡(jiǎn)單思路

將依次將第二個(gè)起都合并到第一個(gè)，復(fù)雜度O（k*n）

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

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

5，擴(kuò)展思路

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

代碼實(shí)現(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            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            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}

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