023.合并K个排序链表.md

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路

通过逐一合并两个链表的思想，在此基础上通过分治的方法进行优化，避免对大部分节点重复遍历多次。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if (lists.length < 2) return lists[0] ? lists[0] : null;
    let interval = 1, length = lists.length;
    while (length > interval) {
        for (let i = 0; i < length - interval; i += 2 * interval) {
            lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
        }
        interval *= 2;
    }
    return lists[0];
};
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let res = new ListNode();
    let curNode = res;
    let node1 = l1, node2 = l2;
    while (node1 && node2) {
        if (node1.val < node2.val) {
            curNode = curNode.next = new ListNode(node1.val);
            node1 = node1.next;
        }
        else {
            curNode = curNode.next = new ListNode(node2.val);
            node2 = node2.next;
        }
    }
    curNode.next = node1 || node2;
    return res.next;
};