[数据结构与算法]leetcode:合并K个升序链表

思路：
1.分治，分成左和右
2.退出条件：0为nil，1为本身
3.两个合并：之前那道题（递归）

src：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    length := len(lists)
    if length == 0 {
        return nil
    }
    if length == 1 {
        return lists[0]
    }
    half := length / 2
    left := mergeKLists(lists[:half])
    right := mergeKLists(lists[half:])
    return mergeTwoLists(left, right)

}

func mergeTwoLists(list1, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }

    if list1.Val < list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    } else {
        list2.Next = mergeTwoLists(list1, list2.Next)
        return list2
    }
}

总结：
两个链就递归，多个链就分治+化为0、1、2链的情况