题目描述

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

示例:

输入:

[

1->4->5,

1->3->4,

2->6

]

输出: 1->1->2->3->4->4->5->6

ListNode数据结构

class ListNode {    int val;    ListNode next;    ListNode(int x) {        val = x;    }}

解决方法

相邻链表两两合并，两两合并详情见

public ListNode mergeKLists(ListNode[] lists) {        int interval = 1;        while (interval < lists.length) {            for (int i = 0; i < lists.length - interval; i += interval * 2) {                lists[i] = merge2Lists(lists[i], lists[i + interval]);            }            interval *= 2;        }        return lists.length > 0 ? lists[0] : null;    }    public ListNode merge2Lists(ListNode l1, ListNode l2) {        if (l1 == null)            return l2;        if (l2 == null)            return l1;        if (l1.val < l2.val) {            l1.next = merge2Lists(l1.next, l2);            return l1;        } else {            l2.next = merge2Lists(l1, l2.next);            return l2;        }    }

时间复杂度： O(Nlogk)，k是链表的数目

本文首发：