题解 | #合并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
    } else if len(lists) == 1 {
        return lists[0]
    } else {
        return mergeTwoLists(mergeKLists(lists[:len(lists)/2]), mergeKLists(lists[len(lists)/2:]))
    }
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	l1 := make([]*ListNode, 0)
	l2 := make([]*ListNode, 0)
	node1, node2 := list1, list2
	for node1 != nil {
		l1 = append(l1, node1)
		node1 = node1.Next
	}
	for node2 != nil {
		l2 = append(l2, node2)
		node2 = node2.Next
	}
	i, j := len(l1)-1, len(l2)-1
	for i >= 0 && j >= 0 {
		if l1[i].Val > l2[j].Val {
			i--
		} else {
			next := l1[i].Next
			l1[i].Next = l2[j]
			l2[j].Next = next
			j--
		}
	}

	var head *ListNode
	if j >= 0 {
		if len(l1) > 0 {
			l2[j].Next = l1[0]
			head = l2[0]
		} else {
			head = list2
		}
	} else {
		if len(l1) > 0 {
			head = l1[0]
		} else {
			head = list1
		}
	}
	return head
}