合并 K个有序列表， 递归解法

//递归解法比较直接好想，不过递归会使用栈空间O(logk)

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
*/
//合并两个有序列表O(n)
func merge(a, b *ListNode ) *ListNode {
    var L ListNode
    var p *ListNode = &L

    for a != nil && b != nil {
        if a.Val <= b.Val {
            p.Next = a
            p = a;
            a = a.Next
            p.Next = nil
        }else {
            p.Next = b;
            p = b;
            b = b.Next;
            p.Next = nil;
        }
    }
    if a != nil {
        p.Next = a;
    }else {
        p.Next = b;
    }

    return L.Next;
}
//递归,利用归并排序思想
func M(lists []*ListNode, L, R int) *ListNode {
    if L > R {
        return nil;
    }
    if L == R {
        return lists[L];
    }
    mid := (L+R)/2;
    L1 := M(lists, L, mid);
    L2 := M(lists, mid+1, R);
    return merge(L1, L2);
}
func mergeKLists( lists []*ListNode ) *ListNode {
    return M(lists, 0, len(lists)-1)
}