知乎ID: 码蹄疾 

码蹄疾，毕业于哈尔滨工业大学。 

小米广告第三代广告引擎的设计者、开发者； 

负责小米应用商店、日历、开屏广告业务线研发；

主导小米广告引擎多个模块重构； 

关注推荐、搜索、广告领域相关知识;

题目

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

示例:

输入:

[

 1->4->5,

 1->3->4,

 2->6

]

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

分析

前面已经做过两个有序链表的合并，只要采用二分，分而治之，两两合并即可。时间复杂度方面，合并两个链表的长度的时间复杂度是o(min(m, n))，其中m，n分别是链表的长度。二合并的长度是o(logk)的时间复杂度。所以整体的时间复杂度为o(klogn)

Code

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null) {            return l2;        }        if (l2 == null) {            return l1;        }        ListNode merged = null;        ListNode head = null;        while (l1 != null && l2 != null) {            if (head == null) {                if (l1.val < l2.val) {                    merged = l1;                    l1 = l1.next;                } else {                    merged = l2;                    l2 = l2.next;                }                head = merged;                continue;            }            if (l1.val < l2.val) {                merged.next = l1;                l1 = l1.next;            } else {                merged.next = l2;                l2 = l2.next;            }            merged = merged.next;        }        while (l1 != null) {            merged.next = l1;            l1 = l1.next;            merged = merged.next;        }        while (l2 != null) {            merged.next = l2;            l2 = l2.next;            merged = merged.next;        }        return head;    }    public ListNode mergeHelper(ListNode[] lists, int low, int high) {        if (low < high) {            int mid = (low + high) / 2;            ListNode leftList = mergeHelper(lists, low, mid);            ListNode rightList = mergeHelper(lists, mid + 1, high);            return mergeTwoLists(leftList, rightList);        }        return lists[low];    }    public ListNode mergeKLists(ListNode[] lists) {        if (lists == null || lists.length == 0) {            return null;        }        return mergeHelper(lists, 0, lists.length - 1);    }}

拓展

合并两个有序链表，之前采用的是非递归的解法。感觉代码有点长，可以采用递归的解法，缩短代码量。合并的时候选最小的元素，链表头指针后移动，递归合并即可。

public class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null && l2 == null) {            return null;        }        if (l1 == null) {            return l2;        }        if (l2 == null) {            return l1;        }        ListNode merged;        if (l1.val > l2.val) {            merged = l2;            l2 = l2.next;            merged.next = mergeTwoLists(l1, l2);        } else {            merged = l1;            l1 = l1.next;            merged.next = mergeTwoLists(l1, l2);        }        return merged;    }}

相关题目