Swift - LeetCode - 合併K個排序連結串列
題目
合併K個排序連結串列
問題:
合併 k 個排序連結串列,返回合併後的排序連結串列。請分析和描述演算法的複雜度。
解題思路:
這裡就需要用到分治法 。簡單來說就是不停的對半劃分,比如k個連結串列先劃分為合併兩個k/2個連結串列的任務,再不停的往下劃分,直到劃分成只有一個或兩個連結串列的任務,開始合併。舉個例子來說比如合併6個連結串列,那麼按照分治法,我們首先分別合併1和4,2和5,3和6。這樣下一次只需合併3個連結串列,我們再合併1和3,最後和2合併就可以了。
示例:
輸入: [ 1->4->5, 1->3->4, 2->6 ] 輸出: 1->1->2->3->4->4->5->6
程式碼:
/** public class SingNode { public var value : Int public var nextNode: SingNode? public init(value:Int) { self.value = value } } **/ func merchageTotalList(_ list : [SingNode?]) -> SingNode? { guard list.count > 0 else { return nil } var left = 0 var right = list.count - 1 var lists = list while right > 0 { left = 0 while left < right { lists[left] = merchgeTwoList(lists[left], lists[right]) left = left + 1 right = right - 1 } } return lists[0] } func merchgeTwoList(_ l1:SingNode?, _l2:SingNode?) -> SingNode? { if l1 == nil { return l2 } if l2 == nil { return l1 } let dummy = SingNode.init(value: 0) var tempNode = dummy var L1 = l1 var L2 = l2 while L1 != nil && L2 != nil { if L1!.value < L2!.value { tempNode.nextNode = L1 L1 = L1?.nextNode } else { tempNode.nextNode = L2 L2 = L2?.nextNode } tempNode = tempNode.nextNode! } tempNode.nextNode = L1 ?? L2 return dummy.nextNode }