/**
 * Definition for singly-linked list.
 * 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]
    }

    num := len(lists) / 2
    l1 := mergeKLists(lists[:num])
    l2 := mergeKLists(lists[num:])
    return mergeTwo(l1, l2)
}

//这里必须写mergerTwo这个函数，不能用mergerKlists([]*ListNode{l1,l2})
func mergeTwo(l1 *ListNode, l2*ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
       l1.Next =  mergeTwo(l1.Next, l2)
       return l1
    }

    l2.Next = mergeTwo(l1, l2.Next)
    return l2
}

//使用分治的思想, 参考leetcode book代码