一、简介

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

要求： 空间复杂度 O(n)，时间复杂度 O(n)

案例1：

输入：
[{1,2,3},{4,5,6,7}]
返回值：
{1,2,3,4,5,6,7}

二、实现

思路：因为N个链表是有序的，比较N个链表第一个节点值，找出最小值，将最小值所在链表往后移动一位，最后将最小值插入到返回链表中。

/*
 * 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
    }
    
    var head = new(ListNode)
    p := head
    for {
        nextNode := getMinNode(lists)
        
        if nextNode == nil {
            break
        }
        
        p.Next = nextNode
        p = nextNode
        
    }
    
    return head.Next
}


// 找出最小节点
func getMinNode(lists []*ListNode ) *ListNode {
	var minIndex = 0
	for k,item := range lists {
		if item == nil { // 排除已为空的链表
			continue
		}

		if lists[minIndex] == nil { // 设置默认值
			minIndex = k
			continue
		}

		if item.Val < lists[minIndex].Val { // 比较
			minIndex = k
		}
	}

	if lists[minIndex] == nil {// 代表链表已经没有节点了
		return nil
	}

	minNode := lists[minIndex]
	lists[minIndex] =   lists[minIndex].Next // 被选中的链表往后移动一位

	minNode.Next = nil
	return minNode
}

题目来源牛客