023-合并K个排序链表 Merge k Sorted Lists

Description

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

Example
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
Solution
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]
    }
    result := lists[0]
    for i := 1; i < len(lists);i ++ {
        result = mergeTwoList(result,lists[i])
    }
    return result
}

func mergeTwoList(left *ListNode,right *ListNode)*ListNode  {
    if left == nil{
        return right
    }
    if right == nil {
        return left
    }
    result := new(ListNode)
    if left.Val > right.Val {
        result = right
        result.Next = mergeTwoList(left,right.Next)
    }else  {
        result = left
        result.Next = mergeTwoList(left.Next,right)
    }
    return result
}




func formatList2Node(list []int)*ListNode  {
    head := new(ListNode)
    current := head
    for i := range list{
        current.Next = new(ListNode)
        current.Next.Val = list[i]
        current = current.Next
    }
    return head.Next
}

leetCode地址