23. 合并K个排序链表

痛定思痛。 2021-12-17 08:53 241阅读 0赞

> 知乎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;
        }
    }

# 相关题目 #

[21. 合并两个有序链表][21.]

![575618-20180715122604739-1822840784.png][]

转载于:https://www.cnblogs.com/acceml/p/9313210.html

[21.]: https://www.cnblogs.com/acceml/p/9282035.html
[575618-20180715122604739-1822840784.png]: /images/20211217/b7c14f65b18c428daeedaea337ee8182.png