Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

148题解决的是2个链表的有序合并，这里是k个～～可以利用之前148题的Merge函数。我们利用分治思想，将k个链表，分成左右两部分分别进行递归合并～

func mergeKLists(lists []*ListNode) *ListNode {

    if len(lists) == 0 {

        return nil

    }

    length := len(lists)

    half := length / 2

    if length == 1 {

        return lists[0]

    }

    if length == 2 {

        l0, l1 := lists[0], lists[1]

        if l0 == nil {

            return l1

        }

        if l1 == nil {

            return l0

        }

        return merge(l0, l1)

    }

    return mergeKLists([]*ListNode{mergeKLists(lists[half:]), mergeKLists(lists[:half])})

}

func merge(left, right *ListNode) *ListNode {

    node := &ListNode{}

    //node会随着新节点的插入一直往后递增

    head := node

    for left != nil && right != nil {

        if left.Val < right.Val {

            node.Next, left = left, left.Next

        } else {

            node.Next, right = right, right.Next

        }

        node = node.Next

    }

    //如果只剩left或者right

    if left != nil {

        node.Next = left

    } else {

        node.Next = right

    }

    return head.Next

}