题解 | #合并k个已排序的链表#

package main

import (
	. "nc_tools"
)
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @return ListNode类
 */
func mergeKLists( lists []*ListNode ) *ListNode {
    // write code here
    if len(lists) == 0 {
        return nil
    }
    return merge(lists,0,len(lists)-1)
}

func merge(lists []*ListNode,left,right int) *ListNode{
    if left == right {
        return lists[left]
    }
    if left > right {
        return nil
    }
    mid := left + (right - left)/2
    return mergeTwoList(merge(lists,left,mid), merge(lists, mid+1, right))
}

func mergeTwoList(head1, head2 *ListNode)*ListNode{
    dummy := &ListNode{}
    tail := dummy
    for head1 != nil && head2 != nil {
        if head1.Val < head2.Val {
            tail.Next = head1
            head1 = head1.Next
        } else {
            tail.Next = head2
            head2 = head2.Next
        }
        tail = tail.Next  
    }
    if head1 != nil {
        tail.Next = head1
    }
    if head2 != nil {
        tail.Next = head2
    }  
    return dummy.Next
}