题解 | #合并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
	}
	if len(lists) == 1 {
		return lists[0]
	}
	minHead := &ListNode{Val: 99999999}
	resHead := minHead

	for {
		// 记录是否还有处理的节点
		tempMin := &ListNode{Val: 99999999}
		index := -1
		// 遍历一遍，确认最小节点
		for i, list := range lists {
			if list == nil {
				continue
			}
			// 确认当前的最小节点
			if list.Val < tempMin.Val {
				tempMin = list
				index = i
			}
		}
		// 没有可操作的节点
		if index == -1 {
			break
		}
		// 对应的链表向前一步
		lists[index] = lists[index].Next
		minHead.Next = tempMin
		minHead = minHead.Next
	}
	return resHead.Next
}